Source-linked AI summary
The total irregularity of a graph
Hosam Abdo, Darko Dimitrov
TL;DR
The paper addresses how to measure graph irregularity beyond existing edge-based measures. It introduces total irregularity, determines graphs maximizing it, and proves that among trees of fixed order, the star uniquely attains the maximum.
Problem
Existing approaches characterize graph irregularity, motivating a measure based on vertex degrees that is determined by the graph’s degree sequence.
Method
The note defines total irregularity from pairwise absolute differences between vertex degrees and analyzes graphs with maximal values.
Results
Among trees with n vertices, irrt(G) ≤ (n − 1)(n − 2), with equality if and only if G is a star graph.
Takeaways & Limitations
Total irregularity is completely determined by degree sequence, and the star is the maximal-total-irregularity tree for each order.
Abstract
from arXiv · showhide
In this note a new measure of irregularity of a simple undirected graph $G$ is introduced. It is named the total irregularity of a graph and is defined as $\irr_t(G) = 1/2\sum_{u,v \in V(G)} |d_G(u)-d_G(v)|$, where $d_G(u)$ denotes the degree of a vertex $u \in V(G)$. The graphs with maximal total irregularity are determined. It is also shown that among all trees of same order the star graph has the maximal total irregularity.
1 Introduction
The note introduces total irregularity as a degree-sequence-based measure of graph irregularity and contrasts it with existing irregularity measures. It motivates the measure by showing that graphs with the same degree sequence can have different irregularities but identical total irregularity.
- 1 Introduction: The note focuses on determining graphs with maximal total irregularity after reviewing bounds and characterizations for existing irregularity measures.
- 1 Introduction: Total irregularity measures graph irregularity using vertex degrees, complementing existing approaches based on degree differences across edges.The paper focuses on a single degree parameter for each vertex.
- 1 Introduction: Graphs with the same degree sequence have the same total irregularity, although their ordinary irregularities may differ.This property is illustrated by two non-isomorphic graphs with degree sequence 1, 1, 1, 1, 2, 3, 3.
- 1 Introduction: For the illustrated graphs, irr(G1) = 10 and irr(G2) = 8, while irrt(G1) = irrt(G2) = 22.
- 1 Introduction: Both irregularity measures are zero exactly for regular graphs, and total irregularity is an upper bound for ordinary irregularity.For connected graphs, prior work gives irrt(G) ≤ n^2irr(G)/4; for trees, irrt(G) ≤ (n − 2)irr(G).
2 Graphs with maximal total irregularity
The paper characterizes graphs maximizing total irregularity through an ordered structure of universal and non-universal vertices, then derives the maximal value and identifies the extremal trees.
- 2 Graphs with maximal total irregularity: A maximizing graph is organized around q universal vertices and an ordered set of non-universal vertices, with adjacency determined by their index sums.The non-universal vertices are ordered by nonincreasing degree, and the neighborhood structure of the first such vertex follows from the preceding conditions.
- 2 Graphs with maximal total irregularity: Edges among ordered non-universal vertices must exist when i + j < n − 2q + 1 and must be absent when i + j > n − 2q + 1.Adding a missing edge in the first range or deleting an existing edge in the second would contradict maximality.
- 2 Graphs with maximal total irregularity: Edges satisfying i + j = n − 2q + 1 may be inserted or deleted without changing total irregularity.These boundary edges account for optional edges in the extremal graphs.
- 2 Graphs with maximal total irregularity: The contribution to total irregularity is decomposed across universal–non-universal, non-universal–non-universal, and remaining vertex pairs before simplification.The resulting maximization produces the displayed closed-form expressions and the extremal graphs shown for orders 4 through 8.
- 2 Graphs with maximal total irregularity: The maximal total irregularity among graphs of order n is attained when q = 1 universal vertex, yielding the stated parity-dependent formulas.For odd n, the resulting value is 1/12(2n^3 − 3n^2 − 2n + 3).
- 2 Graphs with maximal total irregularity: Among trees with n vertices, total irregularity is at most (n − 1)(n − 2), with equality exactly for the star graph.Replacing an edge from a non-central pendant vertex to the maximum-degree vertex increases irregularity until the star is obtained.