2024/11/03 by Martin Knor, Riste Škrekovski, Knor, Martin +5 · 1 citation
Computer Science · Engineering · #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Matrix Theory and Algorithms #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2411.01530
openalex publication_date 2024/11/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The total σ-irregularity is given by σt(G) = ∑_\u,v\ ⊆ V(G) (dG(u) - dG(v))2, where dG(z) indicates the degree of a vertex z within the graph G. It is known that the graphs maximizing σt-irregularity are split graphs with only a few distinct degrees. Since one might typically expect that graphs with as many distinct degrees as possible achieve maximum irregularity measures, we modify this invariant to \IR(G)= ∑_\u,v\ ⊆ V(G) |dG(u)-dG(v)|f(n), where n=|V(G)| and f(n)>0. We study under what conditions the above modification obtains its maximum for antiregular graphs. We consider general graphs, trees, and chemical graphs, and accompany our results with a few problems and conjectures.