Total graph¶

A graph encoding both vertices and edges of a source graph, with adjacency for adjacency or incidence in the source.

Version: v1 · 2026-09-28 · History
Domain-specific #: 12588
Domain group: Formal Sciences
Origin domain: Mathematics
Subdomain: Graph Theory → Mathematics
Aliases: Total graph T(G)

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.

Structural Signature¶

Sig role-phrases:

Source graph — Provides a finite simple undirected graph G with vertex set V and edge set E. It is constitutive. Counterfactual: Without G there is no source whose elements are encoded.
Mixed element vertices — Creates one vertex of T(G) for each member of V∪E, preserving which source element each represents. It is constitutive. Counterfactual: A line graph's edge-only vertex set loses the original vertices.
Same-type adjacency — Connects encoded vertex-vertex and edge-edge pairs when their source elements are adjacent in G. It is constitutive. Counterfactual: Omitting the original-vertex or shared-endpoint edge relation changes T(G).
Cross-type incidence — Connects an encoded source vertex to an encoded source edge when that vertex is its endpoint. It is constitutive. Counterfactual: An incidence-only graph lacks the two same-type adjacency classes.
Interpretive correspondence — Uses the encoding to restate a total coloring of G as a proper vertex coloring of T(G). It is boundary. Counterfactual: A coloring is a use of the graph, not its defining vertex-and-edge construction.

What It Is Not¶

Not total coloring. The graph exists before anyone chooses colors for it.
Not a line graph. T(G) includes encoded source vertices as well as edges.
Not an incidence-only graph. It also records vertex-vertex and edge-edge adjacency.
Not an arbitrary union. The mapping and all three edge rules determine the construction.
Closest near-miss. The line graph L(G) is the nearest miss: it retains edge-edge adjacency but has no encoded original vertices or cross-type incidences.

Scope of Application¶

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¶

Take all vertices and edges of G as new vertices, then connect pairs when the source elements are adjacent or incident. For path a–b–c with edges e,f, T(G) has vertices a,b,c,e,f and seven edges: a–b,b–c,e–f,a–e,b–e,b–f,c–f. A line graph misses a,b,c; an incidence graph misses same-type links. Proper coloring of T(G) is an application equivalent to total coloring of G, not the graph's definition.

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.

Examples¶

Canonical¶

Let G be the three-vertex path a–b–c with edges e=ab and f=bc. T(G) has five vertices a,b,c,e,f. Its seven adjacencies are a–b, b–c, e–f, a–e, b–e, b–f, and c–f. The middle source vertex b is therefore adjacent to both source neighbors and both incident-edge vertices. A proper coloring of this five-vertex graph assigns compatible colors to all original vertices and edges at once.

Mapped back: Source graph → path a–b–c with e=ab and f=bc; Mixed element vertices → a,b,c,e,f; Same-type adjacency → a–b,b–c,e–f; Cross-type incidence → a–e,b–e,b–f,c–f; Interpretive correspondence → proper T(G) coloring yields total coloring of G.

Applied / In Practice¶

Behzad and Chartrand's 1966 paper explicitly introduced the total graph T(G) and analyzed its traversability, comparing it with the older line-graph construction. Their research use treats T(G) as a new graph whose mixed element set and incidence-aware adjacency can be studied for graph paths; it does not make traversability or a particular total coloring a defining property of every T(G).

Mapped back: Source graph → finite simple undirected G in the original paper; Mixed element vertices → paper's points of T(G) correspond to points and lines of G; Same-type adjacency → adjacent point pairs and adjacent line pairs; Cross-type incidence → point-line incidences of G; Interpretive correspondence → graph construction used for traversal analysis; coloring equivalence is another use.

Structural Tensions¶

T1 — Unified Encoding versus Element-Type Distinction. Treating source vertices and edges as one vertex set makes standard graph tools available but can obscure their original kinds.

Diagnostic: Can every total-graph vertex be mapped back to its source element?

T2 — Graph Construction versus Coloring Application. The construction encodes incompatibilities that a proper coloring resolves; a coloring is not required for the graph to exist.

Diagnostic: Is the claim about T(G) itself or one operation performed on it?

Structural–Framed Character¶

The skeleton is a representation mapping source elements into a new graph medium while preserving selected relations. T(G) turns every vertex and edge of finite simple undirected G into a vertex, then links pairs corresponding to adjacency or incidence. Its approved parent is Representation.

Evaluative weight: The construction must use all three relation cases; a loose visualization is insufficient.

Human-practice-bound: Declared graph type and loop/parallel-edge conventions determine variants.

Institutional origin: Graph theory fixes V(G), E(G), adjacency, and incidence definitions.

Vocabulary travels: “Total” in other graph constructions need not mean this T(G).

Import versus recognize: The construction transfers across finite simple graphs; directed or multigraph cases require new conventions.

Its character: A specific graph representation, not a prime for combining all elements.

Structural Core vs. Domain Accent¶

Skeletal core. A source structure can be encoded as another structure whose links preserve specified source relations.

Domain-bound accent. Total graph T(G) uses V(G)∪E(G) as its vertex set and edges for vertex adjacency, edge adjacency, or vertex–edge incidence in G.

Why not prime. Other graph visualizations or transformations may preserve different information. This exact mixed-element mapping defines the named construction.

This entry is a kind of Representation.

Parent — representation. T(G) maps a mixed source structure to an ordinary graph while preserving three specified relations for use in coloring or traversal.
Related — line graph. L(G) retains source edges and their shared-endpoint adjacency but omits source vertices.
Related — total coloring. A proper coloring of T(G) encodes the combined vertex-and-edge coloring constraints of G.

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 (42^nd 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

Not to Be Confused With¶

Total coloring. Tell: Is this the graph carrier or an assignment of colors?
Line graph. Tell: Are original vertices also represented?
Incidence graph. Tell: Are source vertex-vertex and edge-edge adjacencies retained?
Arbitrary graph visualization. Tell: Is there an exact V∪E correspondence and all three link rules?

References¶

Behzad and Chartrand, Total Graphs and Traversability, Proceedings of the Edinburgh Mathematical Society 15 (1966): https://www.cambridge.org/core/journals/proceedings-of-the-edinburgh-mathematical-society/article/total-graphs-and-traversability/C16CD082DC77A146D9C9D64F726AD7A7
Frozen Wikipedia discovery revision: https://en.wikipedia.org/wiki/Total_coloring (revision 1285190354).