Total graph¶
A graph encoding both vertices and edges of a source graph, with adjacency for adjacency or incidence in the source.
Core Idea¶
The total graph T(G) turns both the vertices and the edges of a finite simple undirected source graph G into vertices of a new graph. Two resulting vertices are adjacent precisely if their source elements are adjacent vertices, adjacent edges sharing an endpoint, or an incident vertex-edge pair. Thus it packages three relation types into one ordinary adjacency relation while retaining a mapping back to the original mixed elements.
One use is total coloring: a proper assignment of colors to source vertices and edges under all three conflict rules is just a proper vertex coloring of T(G). The total graph is the carrier of that translation, not the coloring itself. Behzad and Chartrand introduced the construction to study graph traversal, so coloring is not its only research use. A line graph is smaller because it represents only source edges; an incidence graph omits the same-type adjacencies. The source graph's finite simple undirected convention should be stated when using this definition.
Scope of Application¶
The source graph and all three encoded relation types must be recoverable from the constructed graph.
- Graph transformations. Translate mixed vertex-edge constraints into ordinary adjacency.
- Total coloring. Study chromatic conditions as vertex coloring on T(G).
- Traversal research. Analyze paths and cycles in the constructed graph, as in the original study.
- Graph comparison. Distinguish total, line, and incidence constructions by their retained relations.
Clarity¶
T(G) turns every vertex and edge of G into a vertex, then links pairs for source adjacency or incidence. A line graph is the nearest miss because it omits original vertices; an incidence graph omits same-type links. For a–b–c with edges e,f, the mixed vertex set is {a,b,c,e,f}. A proper vertex coloring of T(G) corresponds to total coloring of G, but T(G) exists without any coloring.
Manages Complexity¶
T(G) collapses three kinds of source incompatibility into the single adjacency predicate needed by familiar graph algorithms. The savings come at a price: vertices of T(G) no longer visibly indicate whether they came from V or E unless the mapping is retained. Traversal or coloring results must be translated back through that mapping rather than treated as properties of G without qualification.
Abstract Reasoning¶
- State the finite simple source graph and label each source vertex and edge.
- Create one total-graph vertex for each source element.
- Add links for adjacent source vertices, adjacent source edges, and incident mixed pairs.
- Verify the resulting relation against line and incidence graph near misses.
- Only then apply a graph property such as coloring or traversability and translate it back.
Knowledge Transfer¶
The construction transfers between finite simple graphs because V∪E and the three adjacency/incidence rules remain typed. A result about proper vertex colorings of T(G) can be transferred to total colorings of that same G through the exact correspondence, not by reusing a chromatic value for an unrelated graph. Hypergraphs, directed graphs, or multigraphs require a declared variant because loops, parallel edges, and incidence conventions alter the mapping.
Relationships to Other Abstractions¶
Current abstraction Total graph Domain-specific
Parents (1) — more general patterns this builds on
-
Total graph is a kind of Representation Prime
T(G) represents a graph's mixed vertex-edge elements and three relations in one adjacency medium.
Hierarchy path (1) — routes to 1 parentless root
- Total graph → Representation → Abstraction
Neighborhood in Abstraction Space¶
Total graph sits in a moderately populated region (42nd percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.
Family — Graph Structures & Algorithms (24 abstractions)
Nearest neighbors
- Prism graph — 0.88
- Complete Bipartite Graph — 0.88
- Sierpiński Graph — 0.87
- Utility graph — 0.87
- Graph Power — 0.87
Computed from structural-signature embeddings · 2026-10-08