Edge transmission irregular graphs
2026-07-12 • Discrete Mathematics
Discrete Mathematics
AI summaryⓘ
The authors study a property of graphs where each vertex has a unique 'transmission,' defined as the total distance to all other vertices. They extend this idea to edges by summing the transmissions of their endpoints and call graphs with unique edge transmissions 'edge transmission irregular' (ETI). They find that most graphs are not ETI but show that for every number of vertices 15 or greater, there exists a special type of tree that is both vertex and edge transmission irregular. Their work connects these concepts to chemical graph theory in some cases.
Graph theoryTransmission of a vertexTransmission irregular graphEdge transmissionEdge transmission irregular (ETI)Connected graphSubcubic treeGraph distanceOrder of a graphChemical graph theory
Authors
Kexiang Xu, Ivan Damnjanović, Uroš Milivojević, Sandi Klavžar
Abstract
The transmission of a vertex $v$ in a connected graph $G$ is the sum of distances from $v$ to all vertices in $G$. A transmission irregular (TI) graph is a connected graph in which any two distinct vertices have different transmissions. We extend the concept of transmission to edges by defining the transmission of an edge as the sum of the transmissions of its two endpoints. A connected graph can now be called edge transmission irregular (ETI) if any two distinct edges have different transmissions. We show that almost all graphs are not ETI and then investigate several related order realizability problems involving chemical ETI graphs. In particular, we prove that for every $n \ge 15$, there exists a subcubic tree of order $n$ that is both TI and ETI.