A note: Characterization of star, helm, flower and complete graphs by total vertex stress

1. Introduction

Only, finite, undirected and connected simple graphs are considered. It is assumed that the reader is familiar with the basic notions and notation of graph theory. However, useful definitions will be recalled as is necessary. Unless stated otherwise, reference to vertices \(u,v \in V(G)\) will mean that \(u\) and \(v\) are distinct vertices. When required, the vertices of a graph \(G\) of order \(n \in \mathbb{N}\) will be label as \(v_i\), \(1 \leq i \leq n\). For clarity with regards to notation or undefined concepts in graph theory the reader is referred to [1].

The notion of vertex stress in a graph \(G\) denoted by, \(\mathcal{S}_G(v)\), \(v\in V(G)\) was introduced by the researcher Alfonso Shimbel [2]. The vertex stress of vertex \(v\in V(G)\) is the number of times \(v\) is contained as an internal vertex in all shortest paths between all pairs of distinct vertices in \(V(G)\backslash \{v\}\). Formally stated, \(\mathcal{S}_G(v) = \sum\limits_{u\neq w\neq v\neq u}\sigma(v)\) with \(\sigma(v)\) the number of shortest paths between vertices \(u\), \(w\) which contain \(v\) as an internal vertex. Such a shortest \(uw\)-path is also called a \(uw\)-distance path, see [2,3]. The total vertex stress of \(G\) is given by \(\mathcal{S}(G) = \sum\limits_{v\in V(G)}\mathcal{S}_G(v)\), [4]. Suggested reading which is strongly related to total vertex stress can be found in [3,5,6].

Certain graphs are often grouped as a family of graphs. A family of graphs is defined as those graphs which share a well-defined structural property or a parameter property or other. It is permissible to establish a family of graphs such that, all graphs in the family share a combination of structural and parameter (or invariant) or other properties. For example, all trees are a family of graphs. The structural properties which define this family are: a tree is an undirected graph in which each pair of vertices is connected by exactly one path. However, the family of trees of order \(n \geq 2\) is also a proper subfamily (also referred to as a subset) of the family of \(2\)-colorable graphs. Furthermore, the reader might be familiar with subfamilies (families in their own right). For example, the family of paths and the family of stars are subfamilies of trees. The cycle \(C_3\) belongs to the family of complete graphs and it belongs to the family of cycles and to the family of \(3\)-colorable graphs and to the family of geodetic graphs and others. On the other hand the cycle \(C_5\) does not belong to the family of complete graphs but it belongs to the family of cycles and the family of \(3\)-colorable graphs and the family of geodetic graphs.

Consider two families of graphs denoted by \(\mathcal{F}_1\) and \(\mathcal{F}_2\). Assume an invariant of graphs say, \(\sigma(G)\) is expressed as closed formula in respect of the order \(n\) of the graphs in a specific family of graphs. Let \(\sigma(G) = f_1(n),~\forall n \in \mathbb{N}\), \(G \in \mathcal{F}_1\) and \(\sigma(H) = f_2(n),~\forall n \in \mathbb{N}\), \(H \in \mathcal{F}_2\). It is possible that some graphs of specific order (not all) belong to both \(\mathcal{F}_1\) and \(\mathcal{F}_2\). This means that for specific order i.e. \(n\) for which \(f_1(n) = f_2(n)\). For the purpose of characterization the observation that \(\mathcal{F}_1 \cap \mathcal{F}_2 \neq \emptyset\) could be viewed as contradiction of proof.

If \(\sigma(G) = f_1(n),~\forall n \in \mathbb{N}\), \(G \in \mathcal{F}_1\) is unique to \(\mathcal{F}_1\) on the strict requirement: "for all n" and \(\sigma(H) = f_2(n),~\forall n \in \mathbb{N}\), \(H \in \mathcal{F}_2\) is unique to \(\mathcal{F}_2\) on the strict requirement: "for all n" then the cases where \(f_1(n) = f_2(n)\) are said to be forgiven contradictions. Hence, if \(\sigma(G) = f_1(n),~\forall n \in \mathbb{N}\) is the closed formula for the family of graphs \(\mathcal{F}_1\) on the strict requirement: "for all n" then the statement: \begin{equation}G \in \mathcal{F}_1 iff_f \sigma(G) = f_1(n),~\forall n \in \mathbb{N}, \end{equation} is valid. Note that iff\(_f\) denotes that forgiven contradictions may exist. We state an important lemma;

Lemma 1. For any connected graph \(G\) of order \(n\), a connected predecessor graph \(H\) of order \(n-1\) exists from which \(G\) can be obtained by adding 1 vertex say, \(v_n\) with an appropriate number of well-defined edges with each edge having the vertex \(v_n\) as an end-vertex.

Proof. It is known that a connected graph has at least two vertices which are not cut-vertices, see [1]. Without loss of generality let vertices \(u,v\) be such vertices in a connected graph \(G\). Then graph \(G-u\) or \(G-v\) suffices to be a connected predecessor graph (for brevity, predecessor graph) of \(G\).

2. Characterization of star graphs by total vertex stress

A star graph (for brevity, a star) is a tree which has a central vertex \(v_0\) with \(m \geq 0\) pendent vertices (or leafs) attached to \(v_0\). The star is denoted by \(S_{1,m}\) and let the family of stars be \(\mathcal{F}_1\). Therefore, \(S_{1,0} \cong K_1 \cong P_1\). The star \(S_{1,1} \cong K_2 \cong P_2\) and \(S_{1,2} \cong P_3\). It is known that \(\mathcal{S}(S_{1,m}) = \frac{m(m-1)}{2}\), \(\forall m \in \mathbb{N}_0\).

Theorem 1. A tree \(T \in \mathcal{F}_1\) (or \(T \cong S_{1,m}\)) for some \(m \in \mathbb{N}_0\) iff\(_f\) \(\mathcal{S}(T) = \frac{(n-1)(n-2)}{2}\), \(n = m+1\).

Proof. It is known that in terms of the order \(n = m+1\) of a star, \(\mathcal{S}(S_{1,m}) = \frac{(n-1)(n-2)}{2}\), \(\forall m \in \mathbb{N}_0\). We only have to proof the converse.

It is known that \(\mathcal{S}(K_1) = 0 = \frac{(1-1)(1-2)}{2}\) and \(K_1 \cong S_{1,0}\). All connected graphs of order 1 are accounted for. It is known that \(\mathcal{S}(P_2) = 0 = \frac{(2-1)(2-2)}{2}\) and \(P_2 \cong S_{1,1}\). All connected graphs of order 2 are accounted for. Let \(G = S_{1,1}\) be the predecessor graph from which all possible connected graphs of order 3 can be obtained by adding one vertex with appropriate edges. Also minimize the number of such graphs of order 3 by isomorphism. Hence, the graphs \(S_{1,2}\) or \(C_3\) can be obtained. It is known that \(\mathcal{S}(S_{1,2}) = 1 = \frac{(3-1)(3-2)}{2}\) and \(\mathcal{S}(C_3) = 0 \neq \frac{(3-1)(3-2)}{2}\), \(C_3 \ncong S_{1,2}\). Furthermore, \(C_3\) is not a tree. All connected graphs of order 3 are accounted for. There are six connected graphs of order 4. From the source graphclasses.org/smallgraphs.html\#4nodes we consider each graph.

• (i) The complete graph \(K_4\) has \(\mathcal{S}(K_4) = 0 \neq \frac{(4-1)(4-2)}{2}\), \(K_4 \ncong S_{1,3}\). Also, the predecessor graph is cycle \(C_3\). Furthermore, \(K_4\) is not a tree.
• (ii) The diamond \(D\) has \(\mathcal{S}(D) = 2 \neq \frac{(4-1)(4-2)}{2}\), \(D \ncong S_{1,3}\). Also, the predecessor graph is either \(S_{1,2}\) or \(C_3\). Furthermore, \(D\) is not a tree.
• (iii) The paw (or pan) \(G\) has \(\mathcal{S}(G) = 2 \neq \frac{(4-1)(4-2)}{2}\), \(G \ncong S_{1,3}\). Also, the predecessor graph is either \(S_{1,2}\) or \(C_3\). Furthermore, a paw \(G\) is not a tree.
• (iv) The cycle \(C_4\) has \(\mathcal{S}(C_4) = 4 \neq \frac{(4-1)(4-2)}{2}\), \(C_4 \ncong S_{1,3}\). Also, the predecessor graph is \(S_{1,2}\). Furthermore, \(C_4\) is not a tree.
• (v) The path \(P_4\) has \(\mathcal{S}(P_4) = 4 \neq \frac{(4-1)(4-2)}{2}\), \(P_4 \ncong S_{1,3}\). Also, the predecessor graph is \(S_{1,2}\).
• (vi) The star \(S_{1,3}\) has \(\mathcal{S}(S_{1,3}) = 3 = \frac{(4-1)(4-2)}{2}\). Also, the predecessor graph is \(S_{1,2}\).

For a star \(S_{1,n}\) the predecessor graph is uniquely the star \(S_{1,n-1}\). Clearly the result holds for all trees of order 1, 2, 3 and 4. Assume that the result that, for the family of trees of order \(k\) it holds true that if \(\mathcal{S}(T) = \frac{(k-1)(k-2)}{2}\) then \(T \cong S_{1,k-1}\). Consider a tree \(T\) of order \(k+1\) which by Lemma 1 is obtained from a predecessor graph of order \(k\). Since, \begin{equation} \frac{[(k+1)-1][(k+1)-2]}{2} - \frac{(k-1)(k-2)}{2} = k-1 \end{equation} it implies that each shortest path from say, \(v_k\) to vertices \(v_i\), \(i=1,2,3,\dots,k-1\) accounts for vertex stress equal to 1 and for a neighbor say, \(v_0\) of \(v_k\) the vertex stress count is 0. This is only possible if \(T \cong S_{1,k}\). It is known from [4] that for paths \(\mathcal{S}(P_n) = \frac{n(n-1)(n-2)}{6}\). Utilizing forgiven contradictions for \(n = 1,2,3\) to meet the strict requirement: "for all n" the result \begin{equation} T \in \mathcal{F}_1 (\  or \  T \cong S_{1,m}) \  for \  some \  m \  \in \  \mathbb{N}_0 \  iff_f \  \mathcal{S}(T) = \frac{(n-1)(n-2)}{2}, n = m+1, \end{equation} is settled through induction.

Observe that the forgiven contradictions related to Theorem 1 stem from the fact that:

Case 1: Let \(\mathcal{F}_1 = \{\)stars\(\}\) and \(\mathcal{F}_2 = \{\)paths\(\}\). Then;

\begin{equation} \mathcal{F}_1 \cap \mathcal{F}_2 \neq \emptyset \  and \  neither \  \mathcal{F}_1 \subset \mathcal{F}_2 \  nor \  \mathcal{F}_2 \subset \mathcal{F}_1. \  However; f_1 = f_2 \  for \  some \  n. \end{equation} Furthermore, Theorem 1 is valid for trees of order greater or equal to 1. It is known from [4] that for the family of wheels \(W_n\), \(n \geq 4\) obtained from cycles \(C_n\), \(n \geq 4\) hence, for wheels of order greater or equal to 5, the total vertex stress is given by \(\mathcal{S}(W_n) = \frac{n(n-1)}{2}\). It implies that if connected graphs in general are considered then infinitely many forgiven contradictions exist for Theorem 1 to be viewed valid. The forgiven contradictions stem from the fact that:

Case 2: Let \(\mathcal{F}_1 = \{\)stars\(\}\) and \(\mathcal{F}_2 = \{\)wheels, \(n \geq 4\}\). Then;

\begin{equation} \mathcal{F}_1 \cap \mathcal{F}_2 = \emptyset \  and\  ; f_1 = f_2 \forall n \geq 4. \end{equation} Herein lies the subtlety of the notion of iff\(_f\). Eliminating the infinitely forgiven contradictions can be achieved by an alternative formulation of Theorem 1.

Theorem 2.(Alternative) For a connected graph \(G\) it follows that, \(G \cong S_{1,m}\) or \(W_{m\geq 4}\) for some \(m \in \mathbb{N}_0\) iff\(_f\) \(\mathcal{S}(G) = \frac{(n-1)(n-2)}{2}\), \(n = m+1\).

The proof of Theorem 2 is straight foreword is left for the reader.

In some instances the definition of a graphical structure for conditional \(n \in \mathbb{N}\) say, \(n \geq k\) (or similar), has the inherent property of ambiguousity. It implies that certain graphs may belong to more than one family of graphs. An example is that the path \(P_3\) is also a tree and a star namely, \(S_{1,2}\). On the other hand some definitions of graphical structure has the provisional property of iffness. Iffness means that if the definition is applied, a graph within a specific family is obtained and vice versa. However, iffness is not necessarily absolute and is measured against all known families of graphs. An example of such family of graphs is the helm graphs. Recall that a helm graph (or helm for brevity) is obtained from a wheel by attaching a leaf (pendent vertex) to each rim vertex. Note that a helm graph denoted by \(H_n\) is defined for \(n \geq 3\). The claim is that, measured against all known families of graphs a connected graph \(G\) obtained from the definition of a helm graph as stated, yields a and only a helm graph. Therefore \(G \cong H_n\) for some \(n \geq 3\) and vice versa. For \(n \geq 4\) the result from [4] is that \(\mathcal{S}(H_n) = n(4n+1)\). Since, another unknown family of graphs might be defined in future such that total vertex stress equals \(n(4n+1)\), only an \(f\)-proposition is permissible. Therefore, a \(f\)-statement is stronger than a conjecture in that, it relies on a provisional property. Specialization of a \(f\)-statement might be required in future as was the case with Theorems 1 and 2.

f-Proposition 1. For a connected graph \(G\) of order \(n \geq 4\) it follows that, \(G \cong H_n\) iff\(_f\) \(\mathcal{S}(G) = n(4n+1)\).

Proof. From [4] it is known that \(\mathcal{S}(H_3) = 15\). Since the vertex stress value 15 is not unique it will be excluded. For \(n \geq 4\) the result from [4] is that \(\mathcal{S}(H_n) = n(4n+1)\). The converse follows from the proof of the result in [4]. Because the proof is strictly dependent on a structural analysis of a helm graph, it follows that the result \(\mathcal{S}(H_n) = n(4n+1)\) is strictly structural dependent. Because the definition yields a and only ahelm graph, the result follows from a and only a helm graph. This settles the proof.

By the formal definition of the family of flower graphs (see [4]) it can simply be said that a flower graph \(Fl_n\), \(n \geq 4\) is obtained by adding an edge between each pendent vertex and the central vertex of the corresponding helm graph. An immediate corollary follows;

f-Corollary 1. For a connected graph \(G\) of order \(n \geq 4\) it follows that, \(G \cong Fl_n\) iff\(_f\) \(\mathcal{S}(G) = 2n^2\).

Proof. The result follows by similar reasoning to that in the proof of f-Proposition 1.

In some instances characterization can be stated stronger than an \(f\)-statement despite forgiven contradictions.

Theorem 3. For a connected graph \(G\) of order \(n \geq 1\) it follows that \(G \cong K_n\) iff\(_f\) \(\mathcal{S}(G) = 0\).

Proof. It is known that \(\mathcal{S}(K_n) = 0\), \(n \geq 1\). The inverse follows from the fact that if \(\mathcal{S}(G) = 0\) then, either no shortest path exists or each shortest path is only an edge in \(G\). Hence, \(G\) must be complete.

Forgiven contradictions stem from the fact that \(K_1\) also represents the singleton family (set) containing the trivial graph. The paths \(P_1\) and \(P_2\) serve to show that, \(\{\)complete graphs\(\} \cap \{\)paths\(\} \neq \emptyset\).

Theorem 4. (Thole's theorem)\(^1\) For \(n \geq 3\), let \(\mathcal{F}_2\) be the family of \(K_n-e\), (\(e\) any edge) and \(\mathcal{F}_3\) be the family of \(K_{n-1}(v_i)\multimap v_n\) where \(\multimap v_n\) denotes a single pendent vertex attached to \(K_{n-1}\), (attached to \(v_i\)). It follows that, \[\mathcal{S}(K_n-e) = \mathcal{S}(K_{n-1}\multimap v_n) = n-2 \leq \mathcal{S}(G),\] where \(G\) is a non-complete, connected graph of order \(n\).

Proof. Since \(G\) is connected there exist at least \(\binom{n}{2}\) shortest \(v_iv_j\)-paths in \(G\) with \(v_i,v_j \in V(G) = \{v_k:1\leq k \leq n\}\). The minimum number of shortest \(v_iv_j\)-paths is exactly \(\binom{n}{2}\). Since \(G\) is non-complete it follows that \(\mathcal{S}(G) > 0\), (or put differently, \(\mathcal{S}(G) \geq 1\)). Hence, minimization of total stress requires to have only \(n-2\) shortest paths in \(G\), each of which induces vertex stress of 1. All other shortest paths must be edges in \(G\). It is trivial to state that the only families of graphical embodiments which meet the requirements are \(\mathcal{F}_2\) and \(\mathcal{F}_3\). From the definition of total vertex stress it follows that, \(\mathcal{S}(K_n-e) = \mathcal{S}(K_{n-1}\multimap v_n) = n-2\). Finally, since total vertex stress for non-complete, connected graphs has been minimized it follows that \(\mathcal{S}(G) \geq n-2\).

3. Conclusion

This note introduced the notions of forgiven contradictions, iffness and \(f\)-statements to characterize the family of star, helm, flower and complete graphs by total vertex stress. The concept of iffness is used as a (perhaps vague) qualitative property of graph theoretical definitions and requires deeper debate amongst scholars. Similarly, a deeper understanding of the idea of \(f\)-statements is needed.

Closed formula for the total vertex stress for a number of families of graphs are known, see [3,4,5,6] . Therefore, a wide scope for research exists to characterize other families of graphs by total vertex stress. Furthermore, numerous graph parameters have been studied. The characterization technique can be researched for other graph parameters. Such research could pave the way for parametric characterization of graphs.

3.1. Example: Chromatic characterization

Let \(\mathcal{F}_4\) be the family of complete graphs. With regards to the chromatic number of complete graphs the next chromatic characterization is presented.

Theorem 5. A graph \(G\) of order \(n\) has \(\chi(G) = n\) iff\(_f\) \(G \in \mathcal{F}_4\), (or \(G \cong K_n\)).

Proof. It is known that \(\chi(K_n) = n\). We only proof the converse.

Let \(G\) be of order \(n \in \mathbb{N}\) and let \(\chi(G) = n\). Let \(c(v_i) = c_k\), \(k \in \{1,2,3,\dots,n\}\). From the definition of a proper coloring it follows that since \(c(v_i) = c_k\), a vertex \(v_j \in N_G(v_i)\) has \(c(v_j) \neq c_k\). Moreover, since \(c(v_i)\) cannot be recolored \(c_s\), \(s \in \{c_1,c_2,\dots, c_{k-1}, c_{k+1},\dots, c_n\}\) (else, \(\chi(G) \leq n-1\)) it implies that, \(deg_G(v_i) = n-1\). Therefore, \(deg_G(v_t) = n-1\), \(\forall~v_t \in V(G)\). That settles the result, \(G \in \mathcal{F}_4\), (or \(G \cong K_n\)).

With regards to Theorem 5 another subtlety exists i.e. that no forgiven contradictions exist. Hence, "iff\(_f\)" is as strict as the conventional "iff". Therefore, Theorem 5 is equivalent to the statement: A graph \(G\) of order \(n\) has \(\chi(G) = n\) iff \(G \cong K_n\).

Acknowledgments

The author would like to thank the anonymous referees for their constructive comments, which helped to improve on the elegance of this paper.

Conflicts of Interest

''The author declares no conflict of interest.''