Some Bounds for the Vertex Degree Function Index of Connected Graphs with Given Minimum and Maximum Degrees

Xin Cheng, Xueliang LiMatch 2023 · DOI

This paper, published in MATCH Communications in Mathematical and in Computer Chemistry, provides a unified mathematical framework for bounding a broad class of topological indices used in chemical graph theory. By focusing on the "vertex degree function index," the authors derive tight upper and lower bounds for graphs with fixed minimum and maximum degrees and demonstrate how to construct specific graphs that reach these limits.

TL;DR

The researchers establish a generalized method to calculate the extremal values of any topological index that can be expressed as a sum of vertex degree functions. By leveraging properties of convexity and monotonicity, they provide sharp bounds for connected graphs and prove that these bounds are achievable through specific graph constructions.

What Problem Does This Paper Address?

In chemical graph theory, "topological indices" are numerical values derived from a graph's structure (representing a molecule) that correlate with physical or chemical properties. Historically, researchers have spent decades finding the maximum and minimum values of specific indices—like the Zagreb index or the Randić index—one by one.

The authors identify a redundancy in this approach: the extremal graphs for many different indices are often the same (e.g., paths or stars), and the proof techniques are remarkably similar. This paper addresses the need for a unified mathematical method that can handle a whole set of indices simultaneously, specifically those defined as the sum of some function $f$ of vertex degrees.

Methods

The authors define the vertex degree function index as: $$H_f(G) = \sum_{v \in V(G)} f(d_v)$$ where $d_v$ is the degree of vertex $v$. To find the bounds of this index, they employ several key techniques:

  • Degree Sequence Analysis: They use the fundamental constraints of graph theory—the total number of vertices ($n$) and the Handshaking Lemma (the sum of degrees equals twice the number of edges, $2m$)—to express the number of vertices of minimum degree ($\delta$) and maximum degree ($\Delta$) in terms of other variables.
  • Convexity and Monotonicity: The core of the proof relies on whether the function $f$ is strictly convex or strictly concave. This determines the direction of the bounds.
  • Case-Based Optimization: The authors break down the problem based on how many vertices have degrees between the minimum and maximum values.
  • Graph Construction: To prove the bounds are "sharp" (meaning they can actually be reached), the authors provide two algorithmic constructions using complete $n$-partite graphs and perfect matchings to build graphs that satisfy the equality conditions.

Datasets

Not discussed in the paper. As a theoretical work in mathematical chemistry and graph theory, the paper relies on formal proofs and mathematical derivations rather than empirical datasets or benchmarks.

Key Insights and Ideas

  • The Power of Generalization: By proving theorems for an arbitrary function $f$, the authors effectively solve the extremal problem for dozens of named topological indices at once. If an index fits the $H_f(G)$ form and $f$ is convex, Theorem 1 applies; if $f$ is concave, Theorem 2 applies.
  • Bidegreed Graphs are Extremal: A recurring theme is that the "cleanest" bounds occur when a graph is bidegreed—meaning every vertex has a degree of either exactly $\delta$ or exactly $\Delta$.
  • The "Middle" Degree Impact: The paper shows that the bounds are sensitive to the presence of vertices with degrees between $\delta$ and $\Delta$. They provide specific adjustments to the bounds based on whether the number of these "intermediate" vertices is large or small.
  • Star Graphs as Tree Extremes: For the specific case of trees, the authors confirm the long-standing intuition that the star graph represents the extremal structure for these types of indices.

Key Results

  • Theorem 1 & 2: Provide explicit upper and lower bounds for $H_f(G)$ based on $n, m, \delta, \Delta$, and the specific values of $f$ at those points.
  • Sharpness: The authors prove that their bounds are the best possible by providing a construction method for graphs that hit the exact bound values.
  • Generalization of Prior Work: The results generalize several previous studies, including a 2022 paper that only considered graphs with a maximum degree of four. This work extends those findings to any arbitrary maximum degree $\Delta$.
  • Tree Corollaries: The paper provides simplified versions of the bounds specifically for trees, showing that $H_f(G) \leq (n-1)f(1) + f(n-1)$ for convex functions, with equality holding only for the star graph.

Limitations and Future Work

  • Simple Graphs Only: The study is limited to simple, finite, and connected graphs. It does not account for multigraphs (though they are used as an intermediate step in construction) or directed graphs.
  • Fixed $\delta$ and $\Delta$: The bounds require prior knowledge of the minimum and maximum degrees. In some chemical applications, these parameters might be unknown or variable.
  • Function Constraints: The unified method requires the function $f$ to be strictly monotone and strictly convex/concave. While many chemical indices meet these criteria, those that are "oscillatory" or non-monotonic would require a different approach.
  • Future Directions: The authors suggest that this unified approach could be extended to other classes of indices, such as those based on edge degrees or distance-based metrics.

Summary updated

Abstract

This paper gives some bounds for the vertex degree function index Hf(G) in terms of the order and size of a graph G, where G is a simple, finite and connected graph with minimum degree δ and maximum degree ∆. Some families of graphs are also constructed to show that the bounds can be achieved.
BibTeX
@inproceedings{cheng2023some,
  author = {Xin Cheng and Xueliang Li},
  title = {{Some Bounds for the Vertex Degree Function Index of Connected Graphs with Given Minimum and Maximum Degrees}},
  booktitle = {Match},
  year = {2023},
  doi = {10.46793/match.90-1.175c},
}
Figure