The total graph T(G) of a given graph G is a graph such that the vertex set of T corresponds to the vertices and edges of G and two vertices are adjacent in T if their corresponding elements are either adjacent or incident in G. Can we have non-trivial graphs whose total graphs are complete?
if ei is incident with vi and vi+1 then in the total graph, the vertex corresponding to the edge (ei) is adjacent to vi and vi+1, and will not adjacent to the remaining vertices. Therefore we will not have a complete graph as a total graph.
The only non-trivial graph for which the total graph is complete graph is K2 and the corresponding total graph is K3.
If an endge ei is an hyperedge in a hypergraph then the vertex corresponds to ei in total graph will be adjacent to all remaining vertices.
Then a hypergraph with n-vertices with a single hyperedge e1 which includes all the n-vertices have a total graph which will be a complete graph. but this example also trivial in some sence.
Can you provide an example of a trivial graph and its total graph. I just want to make sure I understand the definition correctly.
Hope to hear back!
Dear Sir,
If the given graph G has n elements (vertex and edges together), then its total graph T contains n vertices, one vertex corresponds to each element of G. Two vertices in T are adjacent if
1. corresponding elements (vertices or edges) are adjacent in G.
2. one of the corresponding element (edge) of G incidents on the other corresponding element (vertex) of G.
Hence, the total graph of a trivial graph (K1) is the trivial graph itself. May I correct my question to non-trivial graphs?
That helps a bit. I meant more like a graph like K_2, or K_3 as they have a small number of vertices and edges.
if ei is incident with vi and vi+1 then in the total graph, the vertex corresponding to the edge (ei) is adjacent to vi and vi+1, and will not adjacent to the remaining vertices. Therefore we will not have a complete graph as a total graph.
The only non-trivial graph for which the total graph is complete graph is K2 and the corresponding total graph is K3.
If an endge ei is an hyperedge in a hypergraph then the vertex corresponds to ei in total graph will be adjacent to all remaining vertices.
Then a hypergraph with n-vertices with a single hyperedge e1 which includes all the n-vertices have a total graph which will be a complete graph. but this example also trivial in some sence.
Dear Natig Aliyev,
Thank you for the answer. But I can not agree with you. The total graph of every complete graph is not a complete graph. Fro example consider complete the graph K4., whose vertices are u, v, w, x. The edges uv and wx are not adjacent inK4 and hence the vertices in T(K4) corresponding these edges in K4 can not be adjacent. Therefore, we can not say that the total graph of every complete graph is a complete graph. K1 and K2 are only the only complete graphs whose total graphs are complete.
What I want is to know whether there is any other graph whose total graph is complete.
So, as Prof. Singaram Dharmalingam pointed out, the only graphs whose total graphs are complete graphs, are K1 and K2.
Thank you all for your valuable inputs.
- Badges
- Science topic
- Similar topics
- Mathematics