Graph Irregularity via Edge Deletions

Basic Information

• Paper ID: 2511.14514
• Title: Graph Irregularity via Edge Deletions
• Authors: Julien Bensmail, Noémie Catherinot, Foivos Fioravantes, Clara Marcille, Nacim Oijid
• Classification: math.CO (Combinatorics), cs.CC (Computational Complexity), cs.DM (Discrete Mathematics)
• Publication Date: November 18, 2025 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/2511.14514

Abstract

This paper investigates the edge irregularity problem of graphs, specifically the parameter Ie(G), which represents the minimum number k of edges that must be deleted to transform graph G into a locally irregular graph (where any two adjacent vertices have different degrees). Although the problem has been proven to be NP-hard and W1-hard, the authors propose two FPT algorithms: one parameterized by solution size plus maximum degree Δ, and another by vertex cover number. Furthermore, the authors conduct in-depth studies on dense graphs, particularly complete graphs, and propose an important conjecture: for any connected graph G with m edges, Ie(G) ≤ m/3 + c, where c is a constant. This conjecture is verified on multiple graph classes, including trees.

Research Background and Motivation

Problem Definition

In graph theory, regular graphs represent graphs where all vertices have the same degree. As a dual concept, researchers have proposed various definitions of irregularity:

1. Irregular graphs: All vertex degrees are pairwise distinct
2. Highly irregular graphs: Each vertex's neighbors have different degrees
3. Locally irregular graphs: Any two adjacent vertices have different degrees

This paper focuses on the concept of locally irregular graphs.

Research Significance

1. Theoretical importance: Local irregularity is an important structural property in graph theory, closely related to the famous 1-2-3 conjecture
2. Operational perspective: Previous research primarily focused on adding edges (such as edge multiplicity) to achieve irregularity; this paper explores the more restrictive operation of edge deletion
3. Parameterized complexity: The problem exhibits rich computational complexity hierarchies, making it suitable for parameterized algorithm research

Limitations of Existing Methods

• Fioravantes et al. 10 recently introduced the concept of edge irregularity subgraphs, proving that computing optimal edge irregularity subgraphs is NP-hard
• The problem is W1-hard with respect to solution size and feedback vertex set
• Behavior on dense graphs (such as complete graphs) and certain structural parameters (neighborhood diversity, distance to clique) remains unclear

Research Motivation

The authors aim to:

1. Design efficient FPT algorithms for specific parameters
2. Understand the exact values or upper bounds of Ie(G) for different graph classes
3. Explore universal relationships between Ie(G) and the number of edges m

Core Contributions

1. Parameterized Algorithms:
   • Propose an FPT algorithm parameterized by solution size k plus maximum degree Δ, with kernel size O(k∆^(2k+2))
   • Propose an FPT algorithm parameterized by vertex cover number vc, with time complexity 2^O(vc^4)·n^O(1), improving previous ILP-based methods
2. Structural Results:
   • Prove exact formulas for Ie on paths and cycles
   • Prove for complete bipartite graphs Kn,m: Ie = 0 when n≠m, Ie = n when n=m
   • Prove for trees T: Ie(T) ≤ |E(T)|/3 (unless T is a path)
   • Provide exact formula for complete graphs of triangular order tk: Ie(Ktk) = |E(Ktk)| - k(k+1)(k-1)(3k+2)/24
3. Important Conjecture (Conjecture 1): There exists a constant c such that for any connected graph G with m edges, Ie(G) ≤ m/3 + c
4. Theoretical Insights:
   • Provide a general lower bound for Ie(G): Ie(G) ≥ ⌈conf(G)/(2∆-1)⌉
   • Prove that edges in optimal edge irregularity subgraphs must be close to conflict edges (Lemma 1)

Methodology Details

Task Definition

Input: Graph G = (V, E) and positive integer k ≥ 1
Output: Determine whether Ie(G) ≤ k (decision version) or compute the optimal edge irregularity subgraph (optimization version)

Definitions:

• Graph G is locally irregular if for any edge uv ∈ E, dG(u) ≠ dG(v)
• Edge irregularity subgraph: Edge set S ⊆ E such that G-S is locally irregular
• Ie(G): Size of the minimum edge irregularity subgraph
• conf(G): Conflict number, the number of edges uv satisfying dG(u) = dG(v)

Core Technical Methods

1. Kernelization Algorithm for k+Δ (Theorem 2)

Key Lemma 1: If S is an optimal edge irregularity subgraph of G, then any edge e in S has distance at most 2|S|-1 to some conflict edge.

Proof Strategy (Induction):

• Base case: When k=1, the unique deleted edge must be adjacent to some conflict
• Inductive step: For k≥2, for any conflict uv, there exists e∈S adjacent to u or v; apply induction hypothesis to G-{e}

Kernelization Rules:

1. If conf(G) ≥ k(2∆+1), return no instance
2. For each conflict edge e, define ball B(e, 2k+1) containing all vertices at distance at most 2k+1 from e's endpoints
3. Construct subgraph H = G∪e∈EC Ve, where Ve is e's ball
4. Adjust vertex degrees in H to match those in G (by adding leaves)

Kernel Size Analysis:

• Number of conflicts |EC| ≤ k(2∆+1)
• Each ball contains at most 2∆^(2k) vertices
• Total vertices: |V(H)| ≤ 2k(2∆+1)∆^(2k+1) = O(k∆^(2k+2))

2. Algorithm for Vertex Cover Number (Theorem 5)

Algorithm Framework:

1. Let C = {u1,...,uvc} be a minimum vertex cover, I = V\C be an independent set
2. Partition I into I1 and I2:
   • I1: Independent set vertices adjacent to some vertex in C with degree ≤ 5vc
   • I2: Remaining independent set vertices
3. Define G1 = GC∪I1, G2 = GC∪I2
4. Enumerate all possible S1 = S∩E(G1) (at most 2^O(vc^4) possibilities)
5. For each S1, compute minimum S2⊆E2 such that G-(S1∪S2) is locally irregular

Key Observation (Claim 7): For any optimal edge irregularity subgraph S consistent with S1, |S∩E2| ≤ vc^2

Optimization Technique (Claim 8): For u∈C and v1,v2∈I2, if uv1∈S but uv2∉S, we can swap to obtain an equivalent optimal solution. Therefore, we only need to guess the number of deleted edges ki for each u∈C, satisfying Σki ≤ vc^2.

Time Complexity: 2^(vc+5vc^2)^2 · vc^(vc^2) · n^2 = 2^O(vc^4) · n^O(1)

Technical Innovations

1. Distance Restriction Technique: Lemma 1 establishes the spatial relationship between edges in optimal solutions and conflicts, which is key to kernelization
2. Degree Preservation Strategy: Preserves degrees by adding leaves, ensuring subproblems are equivalent to the original problem
3. Independent Set Stratification: Stratifies the independent set by neighbor degrees, exploiting the bipartite structure of the graph
4. Swapping Lemma: Proves that which specific edges to independent sets are deleted is unimportant; only the deletion count matters

Experimental Setup

This is a theoretical paper, with results verified primarily through mathematical proofs rather than experiments. However, constructive analysis is performed on multiple graph classes:

Graph Classes Studied

1. Paths Pn and cycles Cn
2. Complete bipartite graphs Kn,m
3. Trees
4. Complete graphs Kn (especially those of triangular order)
5. General connected bipartite graphs
6. General connected graphs

Analysis Methods

• Exact formula derivation: For paths, cycles, specific complete graphs
• Upper bound proofs: For trees, bipartite graphs, general graphs
• Constructive proofs: Demonstrating specific edge irregularity subgraphs achieving bounds
• Recursive algorithms: O(n∆^3) exact computation algorithm for trees

Experimental Results

Main Results

1. Paths and Cycles (Theorem 9)

For paths Pn with n≥2:

• Ie(Pn) = (n-1)/3, when n≡1 (mod 3)
• Ie(Pn) = ⌈(n-1)/3⌉, when n≡2 (mod 3)
• Ie(Pn) = ⌊(n-1)/3⌋, otherwise

For cycles Cn with n≥3: Ie(Cn) = Ie(Pn) + 1

Proof Strategy: Partition the path into consecutive three-edge groups, deleting at least one edge per group

2. Complete Bipartite Graphs (Theorem 10)

• Ie(Kn,m) = 0, when n≠m (already locally irregular)
• Ie(Kn,n) = n (delete all edges of one vertex)

3. Trees (Theorem 13)

Main Theorem: For any tree T, either T is a path or Ie(T) ≤ |E(T)|/3

Proof Strategy:

• For stars and subdivided double stars, delete edges at distance 2 from center
• For general trees, use induction, selecting the deepest vertex of degree ≥3
• Detailed case analysis (by subtree structure and degree)

Algorithmic Result (Theorem 15): Can compute Ie(G) exactly for trees in O(n∆^3) time

4. Complete Graphs (Theorem 16)

For complete graphs of order n = tk = k(k+1)/2 (the k-th triangular number):

Ie(Ktk) = |E(Ktk)| - mk

where mk = k(k+1)(k-1)(3k+2)/24

Construction: The maximum-edge locally irregular graph Tk has degree sequence: 1 vertex of degree n-1, 2 vertices of degree n-2, ..., k vertices of degree n-k

5. Upper Bounds for General Graphs

Bipartite Graphs (Theorem 11): For connected bipartite graphs with minimum degree 1: Ie(G) ≤ n-1

General Graphs (Theorem 12): For any connected graph: Ie(G) ≤ ⌊m/2⌋ + n + ∆ - 2

Conjecture Verification

Conjecture 1: There exists a constant c such that for any connected graph G with m edges, Ie(G) ≤ m/3 + c

Verified Graph Classes:

• ✓ Cycles (c≥2)
• ✓ Trees
• ✓ Complete graphs of triangular order
• ✓ Complete bipartite graphs
• ✓ General graphs satisfy a weaker bound via Theorem 12

Tightness (Theorem 1): For graphs obtained by subdividing each edge of graph H twice: Ie(G) ≥ m/3 Therefore the 1/3 coefficient is tight.

Key Insights

1. Conflict Resolution Efficiency: Deleting one edge resolves at most 2∆-1 conflicts (Remark 1)
2. Connectivity Requirement: Connectivity in Conjecture 1 is necessary (perfect matchings require deleting all edges)
3. Sparse vs. Dense: Sparse graphs (like trees) more easily achieve the m/3 bound; dense graphs (like complete graphs) exhibit complex behavior

Related Work

Research Spectrum on Graph Irregularity

1. Irregular Graphs 6: Chartrand et al. introduced irregularity strength, achieving all different degrees by adding edge multiplicities
2. Highly Irregular Graphs 1,5: Alavi et al. studied graphs where each vertex's neighbors have different degrees
3. Locally Irregular Graphs 2,12:
   • Karoński, Luczak, Thomason proposed the 1-2-3 conjecture (recently resolved by Keusch 13)
   • Baudon et al. studied decompositions of regular graphs into locally irregular subgraphs

Introducing Properties via Deletion Operations

4. Introducing Regularity 3,4:
   • Bazgan et al. achieved degree anonymization via edge rotation
   • Belmonte and Sau studied finding large odd-induced subgraphs
5. Vertex Irregularity Subgraphs 11:
   • Fioravantes et al. introduced achieving local irregularity via vertex deletion
   • Proved FPT algorithms for treewidth and maximum degree
6. Edge Irregularity Subgraphs 10:
   • Recently introduced concept (direct predecessor of this work)
   • Proved NP-hardness and multiple W1-hardness results

Unique Contributions of This Paper

Compared to related work:

• First to propose FPT algorithms for k+Δ and vertex cover number
• First to systematically study exact values for multiple graph classes
• First to propose the m/3+c conjecture with extensive verification
• In-depth study of complete graphs, laying foundation for understanding dense graph parameters

Conclusions and Discussion

Main Conclusions

1. Algorithmic Level: Despite W1-hardness under multiple parameters, FPT algorithms can be obtained through combined parameters (k+Δ) or structural parameters (vertex cover number)
2. Structural Level:
   • Ie(G) can be exactly determined or tightly bounded for multiple graph classes
   • Behavior on trees and sparse graphs is relatively simple
   • Complete graphs exhibit elegant structures related to triangular numbers
3. Theoretical Level: Conjecture 1, if proven, would provide a unified characterization of the asymptotic behavior of Ie(G)

Limitations

1. Incompleteness for Complete Graphs: Only solved for triangular order cases; exact values for general complete graphs Kn remain unknown
2. Constant in Conjecture 1: Although verified on multiple graph classes, the exact value of constant c and general proof remain elusive
3. Algorithm Efficiency:
   • The k+Δ FPT algorithm has exponential dependence on ∆^(2k), limiting practical applications
   • The vertex cover algorithm, while improving ILP methods, still has 2^O(vc^4) dependence
4. Dense Graph Parameters: FPT-status for parameters like neighborhood diversity and distance to clique remains unsolved

Future Directions

Directions explicitly proposed by the authors:

1. Dynamic Conflict Parameters: Improve static conf parameter to dynamically capture conflict evolution
2. Complete Graphs and Cubic Graphs:
   • Determine exact Ie values for general complete graphs Kn
   • Tighten bounds for cubic graphs
3. Extension to k-Degenerate Graphs: Use similar techniques to obtain (k-1)n + ⌊n/3⌋ upper bounds
4. Treewidth Parameterization: The vertex version algorithm from 11 should be adaptable to the edge version
5. Neighborhood Diversity: Requires complete resolution of the complete graph problem first

In-Depth Evaluation

Strengths

1. Theoretical Depth:
   • Elegant proof techniques, particularly Lemma 1's distance restriction and tree induction proofs
   • Kernelization algorithm demonstrates deep understanding of parameterized complexity
   • Complete graph triangular number results reveal deep combinatorial structures
2. Systematicity:
   • Covers multiple graph classes from sparse to dense
   • Combines algorithmic and structural results
   • Integrates theoretical analysis with constructive proofs
3. Conjecture Formulation:
   • Conjecture 1 has strong unifying and inspirational power
   • Verification on multiple graph classes enhances credibility
   • Theorem 1 proves tightness of the 1/3 coefficient
4. Writing Quality:
   • Clear structure, progressing from simple to complex
   • Detailed but non-redundant proofs
   • Illustrations aid understanding (e.g., Figures 3, 4)
5. Practical Algorithms:
   • Tree algorithm O(n∆^3) has polynomial time complexity
   • FPT algorithms provide theoretical guarantees for practical applications

Weaknesses

1. Completeness Gaps:
   • General case for complete graphs unresolved, limiting understanding of dense graphs
   • Conjecture 1 lacks general proof
2. Algorithm Practicality:
   • Double exponential dependence of k+Δ algorithm limits practical application
   • No experimental evaluation of algorithm performance
3. Constant Optimization:
   • Theorem 12's bound ⌊m/2⌋+n+∆-2 may not be tight
   • Exact constant c values for various graph classes not determined
4. Lower Bound Analysis:
   • Beyond conf(G)/(2∆-1), lacks more refined lower bound techniques
   • No discussion of approximation algorithms
5. Parameter Hierarchy:
   • FPT vs. W1-hard boundary not completely characterized
   • Some natural parameters (e.g., treewidth+Δ) unexplored

Impact

1. Theoretical Contribution:
   • Establishes solid foundation for edge irregularity subgraph research
   • Conjecture 1, if proven, would be an important combinatorial result
   • Methods (particularly Lemma 1) may apply to other graph modification problems
2. Follow-up Research:
   • Complete graph problem will attract combinatorists' attention
   • FPT algorithm techniques generalizable to other local properties
   • Provides new perspective on understanding graph local irregularity
3. Practical Value:
   • Tree algorithm directly applicable to network analysis
   • Provides theoretical support for applications like graph anonymization and network robustness
4. Openness:
   • Leaves clear and attractive open problems
   • Multiple difficulty levels suitable for different researchers

Application Scenarios

1. Network Design: Scenarios requiring avoidance of adjacent nodes with identical degrees (e.g., load balancing)
2. Graph Anonymization: Protect privacy by deleting edges to break degree patterns
3. Theoretical Computer Science:
   • Teaching case for parameterized complexity
   • Research paradigm for graph modification problems
4. Combinatorial Optimization: As subproblem in more complex optimization problems

Key References

2 Baudon et al. (2015): Decomposing regular graphs into locally irregular subgraphs
6 Chartrand et al. (1988): Irregular networks, introducing irregularity strength
10 Fioravantes et al. (2024): Introducing edge irregularity subgraphs, proving basic hardness results
11 Fioravantes et al. (2025): Complexity of vertex irregularity subgraphs
12 Karoński et al. (2004): The 1-2-3 conjecture
13 Keusch (2024): Resolving the 1-2-3 conjecture

Overall Assessment: This is a high-quality theoretical computer science paper making substantial contributions at the intersection of parameterized complexity and graph theory. While certain problems (particularly complete graphs) remain incompletely resolved, the paper systematically advances understanding of edge irregularity subgraphs, with the proposed conjecture having important theoretical significance. The methods are novel, proofs rigorous, and future directions clearly outlined. Recommended for publication in top-tier journals in combinatorics or theoretical computer science.