Hostname: page-component-cd9895bd7-fscjk Total loading time: 0 Render date: 2024-12-26T00:59:11.677Z Has data issue: false hasContentIssue false

Total Graphs and Traversability

Published online by Cambridge University Press:  20 January 2009

Mehdi Behzad
Affiliation:
Wayne State University, AND Pahlavi University, Iran,
Gary Chartrand
Affiliation:
The University of Michigan, and Western Michigan University
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

With every graph G (finite and undirected with no loops or multiple lines) there is associated a graph L(G), called the line-graph of G, whose points correspond in a one-to-one manner with the lines of G in such a way that two points of L(G) are adjacent if and only if the corresponding lines of Gare adjacent. This concept was originated by Whitney (3). In a similar way one can associate with G another graph which we call its total graph and denote by T(G). This new graph has the property that a one-to-one correspondence can be established between its points and the elements (the set of points and lines) of G such that two points of T(G) are adjacent if and only if the corresponding elements of G are adjacent (if both elements are points or both are lines) or theyare incident

Type
Research Article
Copyright
Copyright © Edinburgh Mathematical Society 1966

References

REFERENCES

(1) Chartrand, G., The existence of complete cycles in repeated linegraphs, Bull. Amer. Math. Soc. 71 (1965), 668670.CrossRefGoogle Scholar
(2) Ore, O., Theory of Graphs (Providence, 1962).CrossRefGoogle Scholar
(3) Whitney, H., Congruent graphs and the connectivity of graphs, Amer. J. Math. 54 (1932), 150168.CrossRefGoogle Scholar