Graph equation
≈ 3 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In graph theory, Graph equations are equations in which the unknowns are graphs. One of the central questions of graph theory concerns the notion of isomorphism. We ask: When are two graphs the same? (i.e., graph isomorphism) The graphs in question may be expressed differently in terms of graph equations. What are the graphs (solutions) G and H such that the line graph of G is same as the total graph of H? (What are G and H such that L(G) = T(H) ?). For example, G = K 3 , and H = K 2 are the solutions of the graph equation L(K 3 ) = T(K 2 ) and G = K 4 , and H = K 3 are the solutions of the graph equation L(K 4 ) = T(K 3 ). Image: Complete graph K2.svg|::: K_2 Image: Complete graph K3.svg|::: K_3 Image: Complete graph K4.svg|::: K_4 Note that T(K 3 ) is a 4-regular graph on 6 vertices.
In graph theory, Graph equations are equations in which the unknowns are graphs. One of the central questions of graph theory concerns the notion of isomorphism. We ask: When are two graphs the same? (i.e., graph isomorphism) The graphs in question may be expressed differently in terms of graph equations. What are the graphs (solutions) G and H such that the line graph of G is same as the total graph of H? (What are G and H such that L(G) = T(H) ?). For example, G = K 3 , and H = K 2 are the solutions of the graph equation L(K 3 ) = T(K 2 ) and G = K 4 , and H = K 3 are the solutions of the graph equation L(K 4 ) = T(K 3 ). Image: Complete graph K2.svg|::: K_2 Image: Complete graph K3.svg|::: K_3 Image: Complete graph K4.svg|::: K_4 Note that T(K 3 ) is a 4-regular graph on 6 vertices. ==Selected publications== Graph equations for line graphs and total graphs, DM Cvetkovic, SK Simic – Discrete Mathematics, 1975 Graph equations, graph inequalities and a fixed point theorem, DM Cvetkovic, IB Lackovic, SK Simic – Publ. Inst. Math.(Belgrade)., 1976 – elib.mi.sanu.ac.yu, PUBLICATIONS DE L'INSTITUT MATHÉMATIQUE Nouvelle série, tome 20 (34), 1976, Graphs whose complement and line graph are isomorphic, M Aigner – Journal of Combinatorial Theory, 1969 Solutions of some further graph equations, Vasanti N. Bhat-Nayak, Ranjan N. Naik – Discrete Mathematics, 47 (1983) 169–175 More Results on the Graph Equation G2= G, M Capobianco, SR Kim – Graph Theory, Combinatorics, and Algorithms: Proceedings of …, 1995 – Wiley-Interscience Graph equation Ln (G)= G, S Simic - Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat. Fiz, 1975 ==References==
Text derived from https://en.wikipedia.org/w/index.php?oldid=1368870372 under CC BY-SA 4.0; modifications have been made.