Track new results across pure and applied mathematics.
Search papers, labs, and topics across Lattice.
This paper investigates the eccentric subgraph index ($ES(G)$), a novel graph invariant defined as the sum of minimum connected subgraph counts between a vertex and all other vertices. It identifies extremal graphs that maximize $ES(G)$ within specific graph classes, including unicyclic graphs with fixed girth and trees with fixed diameter. The research provides characterizations for graphs maximizing this index under varying structural constraints.
The sum of vertex-pair connected subgraph counts reveals extremal graph structures that defy simple diameter or degree heuristics.
Let $G$ be a connected graph. The eccentric subgraph number $ε(v)$ of a vertex $v$ of $G$ is defined as $ε(v)=\min\{f_G(v,u): u\in V(G)\}$, where $f_G(v,u)$ is the number of connected subgraphs of $G$ containing both $v$ and $u$. The eccentric subgraph index $ES(G)$ of $G$ is defined as $ES(G)=\displaystyle\sum_{v\in V(G)}ε(v).$ In this paper, we obtain the unicyclic graph that maximizes the eccentric subgraph index among all unicyclic graphs on $n$ vertices with a fixed girth. The graph that maximizes the eccentric subgraph index among all unicyclic graphs on $n$ vertices is also obtained. We then characterize the trees that maximize the eccentric subgraph index over trees on $n$ vertices with fixed diameter. Among all connected graphs on $n$ vertices with a fixed number of pendant vertices, the graph which maximizes the eccentric subgraph index is also characterized.