Nordhaus–Gaddum-Type Theorem for Total-Proper Connection Number of Graphs

Wen J. Li, Xueliang Li, Jingshu Zhang

TL;DR

This paper investigates the "total-proper connection number" of graphs, a measure of how efficiently a graph can be "connected" using a specific type of coloring on its vertices and edges. The authors establish a Nordhaus-Gaddum-type inequality for this number, showing a tight bound on the sum of this number for a graph and its complement. This work contributes to understanding graph connectivity properties under advanced coloring schemes.

What Problem Does This Paper Address?

Graph theory often explores how to connect vertices within a graph using various constraints. One such constraint is "coloring," where elements (vertices or edges) are assigned colors. This paper focuses on a specific type of coloring called "total-coloring," where both vertices and edges are colored. The challenge is to ensure that for any two vertices in the graph, there exists a "total-proper path" connecting them. A total-proper path has strict rules: adjacent edges must have different colors, adjacent internal vertices must have different colors, and internal vertices must have colors distinct from their incident edges within the path. The "total-proper connection number," denoted as $tpc(G)$, is the minimum number of colors needed to achieve this total-proper connectivity.

The paper addresses two main questions:

  1. Characterizing graphs with a specific $tpc(G)$ value: They aim to identify which graphs have a total-proper connection number of $n-1$, where $n$ is the number of vertices.
  2. Nordhaus-Gaddum-type inequalities: They seek to establish bounds on the sum of the total-proper connection numbers of a graph $G$ and its complement $\bar{G}$, i.e., $tpc(G) + tpc(\bar{G})$. Nordhaus-Gaddum inequalities are a classic tool in graph theory that relate a graph parameter to its complement.

Methods

The authors employ a combination of theoretical graph analysis and constructive coloring arguments.

  • Characterization of $tpc(G) = n-1$: They analyze properties of graphs that require $n-1$ colors for total-proper connectivity. This involves studying trees, unicyclic graphs, and other graph structures, often by considering their spanning subgraphs and maximum degrees.
  • Nordhaus-Gaddum-type inequalities: To establish bounds for $tpc(G) + tpc(\bar{G})$, they leverage existing results on $tpc(G)$ for specific graph classes (like trees and complete bipartite graphs) and general theorems about graph connectivity. They use inductive arguments and case analysis based on graph properties such as connectivity, presence of cut vertices, and specific structural components (like cycles or complete bipartite subgraphs).
  • Constructive Coloring: For proving upper bounds and demonstrating sharpness, they construct explicit total-colorings of graphs using a specific number of colors. This involves carefully assigning colors to vertices and edges to satisfy the total-proper path conditions.

Datasets

Not discussed in the paper. The paper deals with theoretical graph properties and does not use empirical datasets.

Key Insights and Ideas

  • The "strong property" for total-proper coloring: The paper introduces a concept of a "strong property" for total-proper connected graphs, which is crucial for deriving upper bounds. This property ensures that for any pair of vertices, there are multiple total-proper paths with specific color constraints, which helps in extending connectivity to larger graphs.
  • Connection to graph structure: The value of $tpc(G)$ is shown to be strongly related to the graph's structure, particularly its maximum degree and the presence of cycles or bridges. For instance, trees with a large maximum degree tend to have higher $tpc$ values.
  • Sharpness of bounds: A significant effort is made to show that the established bounds are "sharp," meaning there exist graphs for which the bounds are met. This often involves constructing specific graph families (like double stars or traceable graphs) that achieve these extremal values.
  • Complementary graph behavior: The study of $tpc(G) + tpc(\bar{G})$ reveals interesting relationships between a graph and its complement. For instance, the inequality $tpc(G) + tpc(\bar{G}) \le n+2$ is proven, with equality holding for specific double star graphs.

Key Results

  • Characterization of $tpc(G) = n-1$: A connected graph $G$ of order $n \ge 3$ has $tpc(G) = n-1$ if and only if $G$ is one of the following: a double star $T(2, n-2)$, a cycle $C_4$, $C_4$ with an edge added to non-adjacent vertices ($C_4+e$), or $S_4$ with an edge added to non-adjacent vertices ($S_4+e$).
  • Nordhaus-Gaddum-type inequality: For connected complementary graphs $G$ and $\bar{G}$ on $n$ vertices, the paper proves the inequality $6 < tpc(G) + tpc(\bar{G}) \le n+2$.
  • Lower bound sharpness: The lower bound of 6 for $tpc(G) + tpc(\bar{G})$ is shown to be sharp for $n \ge 4$.
  • Upper bound sharpness: The upper bound of $n+2$ is reached for $n \ge 5$ if and only if $G$ or $\bar{G}$ is a tree with maximum degree $n-2$.
  • Specific cases: For $n=5$, $tpc(G) + tpc(\bar{G})$ is either 6 or 7, depending on whether $G$ is a specific double star graph.

Limitations and Future Work

  • Assumptions on Connectivity: The Nordhaus-Gaddum inequality $6 < tpc(G) + tpc(\bar{G}) \le n+2$ is derived under the assumption that both $G$ and $\bar{G}$ are connected. The paper notes that for complementary graphs, $n$ must be at least 4 for both to be connected.
  • Complexity of $tpc(G)$: Determining the exact $tpc(G)$ for an arbitrary graph is generally a difficult problem. The paper focuses on specific graph classes and general bounds.
  • Future Work: The paper implicitly suggests further exploration of the $tpc$ values for various graph classes and potentially tighter bounds or more general Nordhaus-Gaddum inequalities for this parameter. The characterization of graphs with $tpc(G) = n-1$ also opens avenues for studying graphs with $tpc(G)$ values close to $n-1$.

Summary updated

Abstract

A graph is said to be \emph{total-colored} if all the edges and the vertices of the graph are colored. A path $P$ in a total-colored graph $G$ is called a \emph{total-proper path} if $(i)$ any two adjacent edges of $P$ are assigned distinct colors; $(ii)$ any two adjacent internal vertices of $P$ are assigned distinct colors; $(iii)$ any internal vertex of $P$ is assigned a distinct color from its incident edges of $P$. The total-colored graph $G$ is \emph{total-proper connected} if any two distinct vertices of $G$ are connected by a total-proper path. The \emph{total-proper connection number} of a connected graph $G$, denoted by $tpc(G)$, is the minimum number of colors that are required to make $G$ total-proper connected. In this paper, we first characterize the graphs $G$ on $n$ vertices with $tpc(G)=n-1$. Based on this, we obtain a Nordhaus-Gaddum-type result for total-proper connection number. We prove that if $G$ and $\overline{G}$ are connected complementary graphs on $n$ vertices, then $6\leq tpc(G)+tpc(\overline{G})\leq n+2$. Examples are given to show that the lower bound is sharp for $n\geq 4$. The upper bound is reached for $n\geq 5$ if and only if $G$ or $\overline{G}$ is the tree with maximum degree $n-2$.
BibTeX
@article{li2017nordhausgaddum,
  author = {Wen J. Li and Xueliang Li and Jingshu Zhang},
  title = {{Nordhaus–Gaddum-Type Theorem for Total-Proper Connection Number of Graphs}},
  journal = {Bulletin},
  year = {2017},
  doi = {10.1007/s40840-017-0516-6},
}
Figure