TL;DR
This paper extends the classical Nordhaus-Gaddum problem to the Steiner Harary index, a graph invariant related to distances between subsets of vertices. The authors derive sharp upper and lower bounds for the sum and product of the Steiner Harary index of a graph and its complement, providing a deeper understanding of how these indices behave across different graph structures.
What Problem Does This Paper Address?
The Nordhaus-Gaddum problem is a classic question in graph theory that seeks to find sharp bounds for the sum and product of a graph invariant and its complement. Traditionally, this problem has been studied for invariants like the chromatic number or the clique number. This paper tackles the Nordhaus-Gaddum problem for the Steiner Harary index, a more recent and complex graph invariant. The Steiner Harary index, denoted as $SH_k(G)$, is defined as the average of the Steiner distances of all $k$-subsets of vertices in a graph $G$. The Steiner distance itself is a generalization of the standard graph distance, considering the minimum size of a connected subgraph containing a given subset of vertices. The challenge lies in extending these bounds to this more intricate invariant, especially considering the behavior of both the graph and its complement.
Methods
The paper employs a combination of established graph theory techniques and novel applications of existing results. The core methodology involves:
- Leveraging Steiner Distance Properties: The authors extensively use the definitions and properties of Steiner distance and Steiner diameter, particularly as established in prior works (e.g., Lemmas 1.1-1.5).
- Nordhaus-Gaddum Framework: The paper directly applies the Nordhaus-Gaddum framework, aiming to find bounds for $f(G) + f(\bar{G})$ and $f(G) \cdot f(\bar{G})$, where $f(G)$ is the Steiner Harary index and $\bar{G}$ is the complement graph.
- Case Analysis: For specific values of $k$ (e.g., $k=n$, $k=n-1$, $k=3$), the authors perform detailed case analyses based on graph properties like connectivity and diameter.
- Utilizing Existing Lemmas and Propositions: The proofs heavily rely on previously established lemmas and propositions concerning Steiner distances, Steiner diameters, and specific graph structures (e.g., trees, paths, complete bipartite subgraphs).
- Bounding Techniques: The derivation of bounds involves algebraic manipulation and the application of inequalities derived from the properties of the Steiner Harary index and its relation to Steiner diameter.
Datasets
Not discussed in the paper. The paper focuses on theoretical results for general graphs and specific graph classes, rather than empirical evaluation on datasets.
Key Insights and Ideas
- Generalization of Nordhaus-Gaddum: The paper successfully extends the Nordhaus-Gaddum problem to the Steiner Harary index, a non-trivial generalization that reveals new structural properties of graphs.
- Interplay between Graph and Complement: The bounds derived highlight the intricate relationship between a graph's Steiner Harary index and that of its complement. The sum and product of these indices are constrained by the order of the graph and the chosen subset size $k$.
- Sharpness of Bounds: A significant contribution is the demonstration that the derived bounds are sharp, meaning there exist graphs that achieve these extremal values. This is crucial for the completeness of the Nordhaus-Gaddum results.
- Importance of Graph Structure: The analysis for specific cases (e.g., $k=3$) reveals how graph properties like connectivity, diameter, and the presence of specific subgraphs (like complete bipartite subgraphs) influence the Steiner Harary index and its bounds.
- Foundation for Further Research: The paper provides a solid theoretical foundation for studying Nordhaus-Gaddum-type results for other distance-based topological indices, particularly those involving Steiner distances.
Key Results
The paper establishes sharp upper and lower bounds for the sum and product of the Steiner Harary index of a graph $G$ and its complement $\bar{G}$, denoted as $SH_k(G) + SH_k(\bar{G})$ and $SH_k(G) \cdot SH_k(\bar{G})$, for graphs in the class $G(n)$ (connected graphs with connected complements).
- General $k$ (Theorem 2.1): For $3 \le k \le n$, the paper provides bounds for $SH_k(G) + SH_k(\bar{G})$ and $SH_k(G) \cdot SH_k(\bar{G})$. For instance, the lower bound for the sum is $\frac{1}{2} \max\{k(n-1), (2k-1)^2\}$, and the upper bound for the product is $\left(\frac{n}{k-1}\right)^2$.
- Specific Cases ($k=n, k=n-1, k=3$): The paper refines these bounds for specific values of $k$. For $k=n$ and $k=n-1$, explicit formulas are derived for graphs with certain connectivity properties. For $k=3$, more precise bounds are established, with specific conditions for when these bounds are achieved. For example, for $n \ge 4$, Theorem 3.1 provides bounds for $SH_3(G) + SH_3(\bar{G})$ and $SH_3(G) \cdot SH_3(\bar{G})$ that depend on $n$ and sometimes on the Steiner 3-diameter of $G$.
- Sharpness: The paper demonstrates the sharpness of these bounds through specific examples and constructions, such as paths ($P_n$) and modified star graphs ($S^*$).
Limitations and Future Work
- Class of Graphs: The results are primarily derived for graphs $G$ where both $G$ and its complement $\bar{G}$ are connected. Extending these results to graphs where the complement might be disconnected is a potential avenue for future work.
- Specific Graph Structures: While the paper analyzes specific graph structures (trees, paths, complete bipartite subgraphs) to prove sharpness, a more comprehensive characterization of extremal graphs for all cases could be explored.
- Computational Complexity: The paper focuses on theoretical bounds. Investigating the computational complexity of calculating the Steiner Harary index and its related Nordhaus-Gaddum bounds for arbitrary graphs could be a practical extension.
- Other Graph Invariants: The success in generalizing the Nordhaus-Gaddum problem to the Steiner Harary index suggests that similar investigations could be fruitful for other distance-based topological indices involving Steiner distances.
Summary updated