In
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
, 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
In graph theory, an isomorphism of graphs ''G'' and ''H'' is a bijection between the vertex sets of ''G'' and ''H''
: f \colon V(G) \to V(H)
such that any two vertices ''u'' and ''v'' of ''G'' are adjacent in ''G'' if and only if f(u) and f(v) ar ...
) The graphs in question may be expressed differently in terms of graph equations.
Bibliography on Graph equations
/ref>
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, :::
Image: Complete graph K3.svg, :::
Image: Complete graph K4.svg, :::
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
Vasanti N. Bhat-Nayak was a mathematician whose research concerned balanced incomplete block designs, bivariegated graphs, graceful graphs, graph equations and frequency partitions.
She earned a Ph.D. from the University of Mumbai
The ...
, 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
{{DEFAULTSORT:Graph Equation
Graph theory