Degrees and Connectivities of a Graph and Its δ-Complement

2024/02/04 by Supakorn Srisawat, Srisawat, Supakorn, Panupong Vichitkunakorn +1
Computer Science · Mathematics · #Combinatorics (math.CO) #Computability, Logic, AI Algorithms #FOS: Mathematics #Graph Labeling and Dimension Problems #Rings, Modules, and Algebras

paper · pdf · doi:10.48550/arxiv.2402.02507

openalex publication_date 2024/02/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The δ-complement G_δ of a graph G, introduced in 2022 by Pai et al., is a variant of the graph complement, where two vertices are adjacent in G_δ if and only if they are of the same degree but not adjacent in G or they are of different degrees but adjacent in G. In this paper, we provide the Nordhaus-Gaddum-type bounds, in the spirit of Nordhaus and Gaddum (1956), over the maximum degrees, the minimum degrees, the vertex connectivities, and the edge connectivities of a graph and its δ-complement. All bounds are attained except for the upper bounds on the product between the minimum degrees of a graph and its δ-complement, the vertex connectivities of a graph and its δ-complement, and the edge connectivities of a graph and its δ-complement.

Related

• The connectivity of a bipartite graph and its bipartite complementary graph
• The Weak Version of the Graph Complement Conjecture and Partial Results for the Delta Conjecture
• Proper connection numbers of complementary graphs
• Nordhaus-Gaddum Theorem for the Distinguishing Chromatic Number
• Nordhaus-Gaddum inequalities for the number of connected induced subgraphs in graphs