Contents

Introduction to total chromatic vertex stress of graphs

Author(s): Johan Kok1,2
1Independent Mathematics Researcher, City of Tshwane, South Africa
2Visiting Faculty at CHRIST (Deemed to be a University), Bangalore, India.
Copyright © Johan Kok. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract

This paper introduces the new notion of total chromatic vertex stress of a graph. Results for certain tree families and other \(2\)-colorable graphs are presented. The notions of chromatically-stress stability and chromatically-stress regularity are also introduced. New research avenues are also proposed.

Keywords: Chromatic vertex stress; chromatic equivalent coloring; chromatically-stress stable; chromatically-stress regular

1. Introduction

It is assumed that the reader is familiar with the basic notions and notation of graph theory. However, useful definitions will be recalled when necessary. Reference reading can be found in [1,2]. Only non-trivial, finite, undirected and connected simple graphs are considered. Unless stated otherwise, reference to vertices \(u,v\) (or \(v_i,v_j\)) will mean that \(u\) and \(v\) (or \(v_i\) and \(v_j\)) are distinct vertices.
Alfonso Shimbel [3] introduced the notion of vertex stress in a graph \(G\). This graph parameter is denoted by \(\mathcal{S}_G(v)\), \(v\in V(G)\). 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}\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 [3,4]. The total vertex stress of \(G\) is given by, \[\mathcal{S}(G) = \sum\limits_{v\in V(G)}\mathcal{S}_G(v),\][5] .
The work in [3] has been extended significantly in [6,7].
Hereafter it will be assumed that the vertices of a graph \(G\) are labeled so that \(V(G) = \{v_i:1\leq i \leq n, n \geq 2\) the order of \(G\}\). For a set of (distinct) colors \(\mathcal{C}= \{c_1,c_2,c_3,\dots,c_\ell\}\) a vertex coloring of a graph \(G\) is an assignment \(\varphi:V(G) \mapsto \mathcal{C}.\) A vertex coloring is said to be a proper vertex coloring of a graph \(G\) if no two distinct adjacent vertices have the same color. The cardinality of a minimum set of distinct colors in a proper vertex coloring of \(G\) is called the chromatic number of \(G\) and is denoted by, \(\chi(G).\) We call such a coloring a \(\chi\)-coloring or a chromatic coloring of \(G.\) A chromatic coloring of \(G\) is denoted by, \(\varphi_\chi(G)\). Generally a graph \(G\) of order \(n\) is \(k\)-colorable for \(\chi(G) \leq k \leq n.\) Furthermore, the number of distinct \(k\)-colorings (permutations permitted) is enumerated by the corresponding chromatic polynomial of a graph. For \(k\)-colorings the chromatic polynomial is denoted by, \(\mathcal{P}_G(k, n)\). It implies that for a specific graph \(G\) (so specific order \(n\)) and a specific value \(k\) thus, say \(\mathcal{P}_G(k, n) = \ell\), there exist \(\ell\) distinct \(k\)-colorings denoted by, \(\varphi_k^1, \varphi_k^2, \dots, \varphi_k^\ell\). Hence, a \(k\)-coloring of a graph \(G\) is not necessarily unique. See [8,9] for a good overview of chromatic polynomials.
Vertex stress as defined by Shimbel [3] allocates a stress count of 1 to a vertex each time it is an internal vertex on some shortest path (distance path) in graph \(G\). Hence, it is a \(0-1\) binary function. In some applications, transiting different vertices could present different stress. In this study differentiation of stress is represented by coloring. Also the incremental stress induced along a colored distance path is allocated to the departure vertex \(v_i\) in respect of all shortest paths along a shortest \(v_iv_j\)-path. Furthermore, internal vertices of the same color as the departure vertex do not present any stress to the departure vertex \(v_i\). Consider a graph \(G\) and any \(\varphi_k^t(G)\), \(1 \leq t \leq \ell\) as well as any two vertices \(v_i, v_j \in V(G)\). The coloring vertex stress in respect of \(v_i\) along all shortest \(v_iv_j\)-paths for all \(j = 1,2,3,\dots, i-1,i+1,\dots,n\) is the sum of the number of times a color \(c_l \neq c(v_i)\) appears as an internal vertex color on each shortest \(v_iv_j\)-path. This parameter is denoted by \(\mathfrak{s}_{\varphi_k^t(G)}(v_i)\). Note that in respect of a particular \(v_iv_j\)-path and the inverse \(v_jv_i\)-path, the values \(\mathfrak{s}_{\varphi_k^t(G)}(v_i)\) and \(\mathfrak{s}_{\varphi_k^t(G)}(v_j)\) are not necessarily equal. Finally, the total coloring vertex stress of a graph \(G\) in respect of \(\varphi_k^t(G)\) is defined by, \[\mathcal{S}_{\varphi_k^t}(G) = \sum\limits_{i=1}^{n}\mathfrak{s}_{\varphi_k^t(G)}(v_i).\]

For a graph \(G\) of order \(n\), bounds which are a direct consequence from the definitions above are stated as a corollary for \(k\)-colorings, \(\chi(G) \leq k \leq n\). It requires no further proof.

Corollary 1. For a \(k\)-coloring of a graph \(G\) of order \(n\), \[\mathcal{S}(G) \leq \mathcal{S}_{\varphi_k^t}(G) \leq 2\mathcal{S}(G), 1 \leq t \leq \ell.\]

Note that for any specific value of \(k\) (specific \(k\)-coloring) there is no obvious relationship between \(\mathcal{S}_{\varphi_k^{t_1}(G)}\) and \(\mathcal{S}_{\varphi_k^{t_2}(G)}\), \(1 \leq t_1,t_2 \leq \ell\). It is evident that for the general range \(1 \leq t \leq \ell\) a maximum and minimum value may exist. Hence, the vast variety of colorings for each possible \(k\)-coloring of a graph in general requires coded computational algorithms for in-depth research of coloring vertex stress.

2. Total chromatic vertex stress

By setting \(k = \chi(G)\) the number \(\mathcal{P}_G(\chi, n) = \ell\) of distinct \(\chi\)-colorings of a graph can be enumerated.

Definition 2. Consider a graph \(G\) for which \(\mathcal{P}_G(\chi, n) \geq 2\) and any two \(\chi\)-colorings say, \(\varphi_\chi^1(G)\) and \(\varphi_\chi^2(G)\). If \(\mathfrak{s}_{\varphi_\chi^1(G)}(v_i) = \mathfrak{s}_{\varphi_\chi^2(G)}(v_i)\), \(\forall \varphi_\chi^1, \varphi_\chi^2\) then \(G\) is said to be chromatically-stress stable in respect of a \(\chi\)-coloring.

Definition 2 implies that if a graph \(G\) is chromatically-stress stable then all \(\chi\)-colorings are chromatically equivalent meaning that color classes may simply be interchanged sufficiently to obtain all possible \(\chi\)-colorings. A trivial example is a complete graph \(K_n\), \(n \geq 2\). It is known that the chromatic polynomial is given by,

\(\mathcal{P}_{K_n}(n, n) = \prod\limits_{i=0}^{n-1}(n-i)\).

Equally easy it follows that all \(\varphi_n^t(K_n)\), \(1 \leq t \leq \prod\limits_{i=0}^{n-1}(n-i)\) are chromatically equivalent and for any \(v_i \in V(K_n)\), \(\mathfrak{s}_{\varphi_n^t(K_n)}(v_i) = 0\). Hereafter the paper will be restricted to certain \(2\)-colorable graphs. Researching the range of values of total chromatic vertex stress for graphs \(G\) with \(\chi(G) \geq 3\) remains open.

Theorem 3. For a connected, \(2\)-colorable graph \(G\) all \(\chi\)-colorings are chromatically equivalent. Therefore, \(2\)-colorable graphs are chromatically-stress stable.

Proof. All graphs under consideration are connected. The result follows from the fact that, without loss of generality (interchanging colors \(c_1, c_2\) is permitted) and up to isomorphism of labeled graphs a connected \(2\)-colorable graph has a unique coloring. ◻

It is known that a graph is \(2\)-colorable if and only if it is a bipartite graph. Hence, a connected \(2\)-colorable graph \(G\) has a unique vertex partition say \(V(G) = X \cup Y\) such that if vertices \(v_i,v_j \in X\) then edge \(v_iv_j \notin E(G)\) and if vertices \(u_i,u_j \in Y\) then edge \(u_iu_j \notin E(G)\). For \(2\)-colorable graph the contributory chromatic vertex stress of vertex \(v_i\) and denoted by \(\mathcal{s}_{\varphi_\chi(G)}(v_i)\) is the proportional chromatic vertex stress induced by vertex \(v_i\) in respect of only vertices \(v_j\), \(i+1 \leq j \leq n\). Then \(\mathcal{S}_{\varphi_\chi}(G) = 2\times\sum\limits_{i=1}^{n}\mathcal{s}_{\varphi_\chi(G)}(v_i)\). The aforesaid is efficient for CIT-coding in respect of large graphs.

2.1. Certain classes of trees.

The classification below is not a partition hence, some categories (or families) are sub-categories of others. It is merely the specialization of structure which motivates the classification. When \(k\), \(k\geq 1\) leafs (or pendent vertices) are attached to a selected vertex \(v_i\) it is said that a \(k\)bunch of leafs has attached to \(v_i\).
(a) A non-trivial path \(P_n\), \(n \geq 2\) is a tree with exactly two leafs. By convention a path will have its vertices consecutively labeled from left to right as \(v_1,v_2,v_3,\dots, v_n\).
(b) A star \(S_{1,n}\), \(n\geq 3\) (sub-category of spiders) has a central vertex \(v_0\) with \(n\) leafs adjacent to \(v_0\).
(c) A \(\ell\)-star \(S_{\ell,n\star m}\), \(\ell \geq 2\), \(n,m\geq 2\) has a path \(P_\ell =v_1v_2v_3\cdots v_\ell\) with a \(n\)-bunch of leafs attached to say, \(v_1\) and a \(m\)-bunch of leafs attached to \(v_\ell\).
(d) A spider \(S^\ast_n\), \(n\geq 3\) is a starlike tree with one vertex \(v_0\) of degree \(n\) and all other vertices have degree at most \(2\). Clearly, \(S^\ast_n\), \(n\geq 3\) has \(n\) pendent vertices. Hence in this context \(n\) does not mean the order of a spider. Put differently, a spider has a central vertex \(v_0\) which is attached with an edge to exactly one end-vertex of each path \(P_{m_1}, P_{m_2},\dots, P_{m_t}\), \(t\geq 3\).
Note that for a given \(n\), all possible paths \(P_n\) are isomorphic (both the graph structure and the resultant graph are well-defined). Similarly, for a given \(n, m, \ell\) a star and a \(\ell\)-star are well-defined in respect of both the graph structure and the resultant graph. For given \(k\) and \(d\) a \((k,d)\)-regular tree is also well-defined in respect of both the graph structure and the resultant graph. Therefore, closed results or efficient algorithms for the total chromatic vertex stress can be determined. On the contrary, spiders, caterpillars and lobsters are considered to be well-defined only in respect of graph structure. In this section results for the total chromatic vertex stress of paths, stars, \(\ell\)-stars and spiders will be presented. The purpose is to establish important enumeration techniques.

Proposition 4. A non-trivial path \(P_n\), \(n \geq 2\) has: \[\mathcal{S}_{\varphi_\chi}(P_n) = \begin{cases} \frac{t(t+1)(4t+5)}{3}, t = \frac{n}{2}-1, & \mbox{if $n$ is even};\\ \frac{t(t+1)(4t-1)}{3}, t = \lfloor \frac{n}{2}\rfloor, & \mbox{if $n$ is odd.} \end{cases}\]

Proof. Part 1. For path \(P_2\) it is easy to see that \(\mathcal{s}_{\varphi_\chi(P_2)}(v_1) = \mathcal{s}_{\varphi_\chi(P_2)}(v_2) = 0\). Therefore \(\mathcal{S}_{\varphi_\chi}(P_2) = 0\). For path \(P_4\) it is easy to see that \(\mathcal{s}_{\varphi_\chi(P_4)}(v_1) = \mathcal{s}_{\varphi_\chi(P_4)}(v_4) = 2\). Also \(\mathcal{s}_{\varphi_\chi(P_4)}(v_2) = \mathcal{s}_{\varphi_\chi(P_4)}(v_3) = 1\). Therefore \(\mathcal{S}_{\varphi_\chi}(P_4) = 6\). Through immediate induction it follows that if \(n \geq 4\) and \(\mathfrak{s}_{\varphi_\chi(P_n)}(v_1) = k_1\) then \(\mathcal{s}_{\varphi_\chi(P_{n+2})}(v_1) = k_1 + n\). Similarly, if \(\mathcal{s}_{\varphi_\chi(P_n)}(v_2) = k_2\) then \(\mathcal{s}_{\varphi_\chi(P_{n+2})}(v_2) = k_2 + (n-1)\) and so on. For \(n \geq 2\) the aforesaid patterns yield the sequence \(0,3,13,34,70,125,203,\dots\) for the values of \(\mathcal{S}_{\varphi_\chi}(P_n)\). It corresponds to the closed formula \(a(i) = \frac{i(i+1)(4i+5)}{6}\), \(i=0,1,2,3,\dots\). See integer sequence A016061 listed in the On-line Encyclopedia of Integer Sequences. Hence, for the application to paths \(P_n\), \(n \geq 2\) and \(n\) is even the transformation formula \(t = \frac{n}{2}-1\) is required. This settles the first result, i.e. \(n \geq 2\) and even.
Part 2. The reasoning we utilize is the fact, that each odd path say \(P_{n+1}\) can be associated with a preceding even path \(P_n\). From Part 1 and through similar reasoning to extend an even path \(P_n\) to an odd path \(P_{n+1}\), the sequence \(0,1,7,22,50,95,161,\dots\) develops in respect of \(\mathcal{S}_{\varphi_\chi}(P_{n+1})\) for odd paths. This sequence corresponds to the sequence A002412. By letting \(n = 3,5,7,\dots\) and using the transformation formula \(t = \lfloor \frac{n}{2}\rfloor\) the second result is settled, i.e. \(n \geq 1\) and odd. ◻

Remark: Admittedly some readers might not find the argument of immediate induction in the proof of Proposition 4 sufficiently rigorous. The substitution of that reasoning with a formal induction approach is left to the reader.

Corollary 5. A path \(P_n\), \(n \geq 2\) has \(\mathfrak{s}_{\varphi_\chi(P_n)}(v_1) = 2\lfloor \frac{(n-1)^2}{4}\rfloor\).

Proof. The result is a direct consequence of the proof of Proposition 4. ◻

Proposition 6. A star \(S_{1,n}\), \(n\geq 3\) has \(\mathcal{S}_{\varphi_\chi}(S_{1,n}) = n(n-1)\).

Proof. Let the \(n\) leafs be colored \(c(v_i) = c_1\), \(i = 1,2,3,\dots, n\) and \(c(v_0) = c_2\). It follows easily that each leaf has \(\mathcal{s}_{\varphi_\chi(S_{1,n})}(v_i) = n – 1\). Also \(\mathcal{s}_{\varphi_\chi(S_{1,n})}(v_0) = 0\). By definition \(\mathcal{S}_{\varphi_\chi}(S_{1,n}) = n(n-1)\). ◻

Proposition 7. Let \(t = \frac{\ell}{2} – 1\) if \(\ell\) is even, and \(t = \lfloor \frac{\ell}{2}\rfloor\) if \(\ell\) is odd. Then a \(\ell\)-star \(S_{\ell,n\star m}\), \(\ell \geq 2\), \(n,m\geq 2\) has:
\[\mathcal{S}_{\varphi_\chi}(S_{\ell,n\star m}) =\] \[\begin{cases} n(n-1) + m(m-1) + 2(A_1 + B_1) + \frac{t(t+1)(4t+5)}{3}& \mbox{if $\ell$ is even};\\ n(n-1) + m(m-1) + 2(A_2 + B_2) + \frac{t(t+1)(4t-1)}{3} & \mbox{if $\ell$ is odd.} \end{cases}\] where \(A_1 = A_2 = n\lfloor \frac{(\ell+1)^2}{4}\rfloor + n(m-1)\lceil \frac{\ell}{2}\rceil\), \(B_1 = B_2 = m\lfloor \frac{\ell^2}{4}\rfloor\).

Proof. Note that the induced subgraphs \(\langle N[v_1]\backslash \{v_2\}\rangle\) and \(\langle N[v_\ell]\backslash \{v_{\ell-1}\}\rangle\) are stars. Using Proposition 6 the first two terms in both parts follow. Label the \(n\)-bunch of leafs at vertex \(v_1\) say, \(u_i\), \(i = 1,2,3,\dots,n\) and the \(m\)-bunch of leafs at vertex \(v_\ell\) say, \(w_j\), \(j = 1,2,3,\dots,m\).
Part 1. The term \(A_1\) is obtain from firstly, the chromatic vertex stress induced by vertex \(u_i\) along the \(u_iw_1\)-paths \(\forall~i\). The aforesaid follows from Corollary 5. Since all shortest paths between \(u_i\) to each vertex \(v_j\), \(j = 1,2,3,\dots,\ell\) have been accounted for, the only paths to further consider are the \(1\)-count along paths \(u_iw_j\), \(i = 1,2,3,\dots,n\) \(j = 2,3,4,\dots,m\). The aforesaid yields the value \(n(m-1)\lceil \frac{\ell}{2}\rceil\).
Part 2. The term \(B_1\) follows from the \(m\), \(w_iv_1\)-distance paths. Proposition 6 is applied to obtain the chromatic vertex stress induced by each \(w_i\). Therefore, the term \(B_1\) is established.
Finally, the last term accounts for the total chromatic vertex stress for the \(v_1v_\ell\)-path. The distinction between odd and even \(\ell\) follows from Proposition 4. The fact that \(\mathcal{S}_{\varphi_\chi}(G) = 2\times\sum\limits_{i=1}^{n}\mathcal{s}_{\varphi_\chi(G)}(v_i)\) settles the result. ◻

Proposition 8. A spider \(S^\ast_n\),, \(n\geq 3\) has: \[\mathcal{S}_{\varphi_\chi}(S^\ast_n,) = 2\times[\sum\limits_{i=1}^{t-1}\sum\limits_{j=i+1}^{t}\mathcal{S}_{\varphi_\chi}(P_{(m_i+m_j+1)}) – (t-2)\sum\limits_{k=1}^{t}\mathcal{S}_{\varphi_\chi}(P_{(m_k+1)})].\]

Proof. Clearly, to account for all shortest paths in \(S^\ast_n\) the \(\frac{t(t-1)}{2}\) paths of order \((m_i+m_j+1)\), \(i = 1,2,3,\dots,(t-1)\) and \(j = i+1, i+2,i+3,\dots,t\) must be accounted for. However, multi counting of chromatic vertex stress in respect of paths \(P_{(m_k+1)}\), \(k = 1,2,3,\dots,t\) occurs. The multi-counting is corrected by the subtraction of the second term. Thus the result follows from the utilization of Proposition 4 and the fact that \(\mathcal{S}_{\varphi_\chi}(G) = 2\times\sum\limits_{i=1}^{n}\mathcal{s}_{\varphi_\chi(G)}(v_i)\). ◻

3. Certain \(2\)-colorable graphs which are not trees

We provide the result for even cycles.

Proposition 9. A cycle \(C_n\), \(n \geq 4\) and \(n\) is even has: \[\mathcal{S}_{\varphi_\chi}(C_n) = n\lfloor \frac{(t-1)^2}{4}\rfloor,~ t =\frac{n+2}{2}.\]

Proof. Since \(n\) is even, \(\chi(C_n) = 2\). From Corollary 5 it follows that for \(t \geq 3\), \(\mathcal{s}_{\varphi_\chi(P_t)}(v_1) = \lfloor \frac{(t-1)^2}{4}\rfloor\). For an even cycle, \(diam(C_n) = \frac{n+2}{2}\). The fact that a cycle is a vertex-transitive graph read with the definition of the total chromatic vertex stress of a graph yields the result, \(\mathcal{S}_{\varphi_\chi}(C_n) = n\lfloor \frac{(t-1)^2}{4}\rfloor,~ t =\frac{n+2}{2}\). ◻

Complete bipartite graphs \(K_{n,m}\), \(n \geq 2\), \(m \geq 3\) will be considered. Those complete bipartite graphs which are excluded have been dealt with under a category either trees or the cycle \(C_4\).

Proposition 10. A complete bipartite graph \(K_{n,m}\), \(n \geq 2\), \(m \geq 3\) has: \[\mathcal{S}_{\varphi_\chi}(K_{n,m}) = nm(m-1) + mn(n-1).\]

Proof. By definition a connected bipartite graph \(G\) has an unique vertex partition say, sets \(X\) and \(Y\) such that both \(X,Y\) are independent sets. Let \(|X| = n\), \(|y| = m\). Furthermore, a complete bipartite graph \(K_{n,m}\) is a connected \(2\)-diam graph. Let \(X = \{u_i: 1\leq i \leq n\}\) and \(Y = \{v_j:1\leq j \leq m\}\). It follows that \(\forall~i\) and \(\forall~j\) all the shortest \(u_iv_j\)-paths are edges. Hence, along all the shortest \(u_iv_j\)-paths the total induced chromatic vertex stress is \(0\). There are \(\binom{n}{2}\) pairs of distinct vertices \(u_i,u_k\) and for each pair there are \(m\) shortest \(u_iu_k\)-paths of distance \(2\). Similarly, there are \(\binom{m}{2}\) pairs of distinct vertices \(v_j,v_t\) and for each pair there are \(n\) shortest \(v_jv_t\)-paths of distance \(2\). Since, \(K_{n,m}\) is \(2\)-colorable each such shortest path induces chromatic vertex stress of \(1\). Hence by the definition, \[\mathcal{S}_{\varphi_\chi}(K_{n,m}) = nm(m-1) + mn(n-1).\] ◻

3.1. Generalization: Complete \(m\)-partite graphs

The result of Proposition 10 permits an immediate generalization.

Corollary 11. A complete \(m\)-bipartite graph \(K_{n_1,n_2,\dots,n_m}\), \(n_i \geq 1\) \(\forall~i\), \(m \geq 2\) has: \[\mathcal{S}_{\varphi_\chi}(K_{n_1,n_2,\dots,n_m}) = \sum\limits_{i=1}^{m}\sum\limits_{\substack{j=1 \\ j\neq i}}^{m}n_jn_i(n_i-1).\]

Note that for \(n_i = 1\) \(\forall~i\) the graph \(K_{n_1,n_2,\dots,n_m} \cong K_m\).

4. Conclusion

This paper introduced the notion of total chromatic vertex stress in a graph. In particular, results for certain \(2\)-colorable graphs were presented. New avenues for research are suggested.

Definition 12. Consider a graph \(G\) and a specific \(\chi\)-coloring say, \(\varphi_\chi^t(G)\). If \(\mathfrak{s}_{\varphi_\chi^t(G)}(v_i) = \mathfrak{s}_{\varphi_\chi^t(G)}(v_j)\), \(\forall v_i,v_j \in V(G)\) then \(G\) is said to be chromatically-stress regular in respect of the specific \(\chi\)-coloring.

If Definition 12 is valid \(\forall~ \varphi_\chi^t(G)\), \(1\leq t \leq \ell\) then \(G\) is said to be strongly chromatically-stress regular. An example of a strongly chromatically-stress regular graph is any even cycle \(C_n\). These new notions are considered worthy research avenues.
It is known that the Petersen graph \(P^\star\) has,

\(\mathcal{P}_{P^\star}(k, 10) = k(k-1)(k-2)(k^7 – 12k^6 + 67k^5 -230k^4 +529k^3 – 814k^2 +775k – 352).\)

Proposition 13. The Petersen graph is chromatically-stress stable and strongly chromatically-stress regular.

Proof. Part 1. It is known that the Petersen graph is geodetic, \(3\)-regular and of diameter 2 and \(\chi(P^\star) = 3\). Therefore, for any proper \(3\)-coloring and a distance \(d(v_i,v_j)\)-path of length \(2\) the internal vertex say, \(v_k\) is in \(N(v_i)\) (and in \(N(v_j)\)). Thus over all shortest paths, \(\mathfrak{s}_{\varphi_\chi^1(P^\star)}(v_i) = \mathfrak{s}_{\varphi_\chi^2(P^\star)}(v_i)\) for all \(\chi\)-colorings. Hence, \(P^\star\) is chromatically-stress stable.
Part 2. Each vertex \(v_i \in V(P^\star)\) has \(3\) neighbors (distance paths of length \(1\)) and \(6\) distance paths of length \(2\). Thus, over all \(\chi\)-colorings we have \(\mathfrak{s}_{\varphi_\chi^t(P^\star)}(v_i) = 6\), \(v_i \in V(P^\star)\). This settles the claim that \(P^\star\) is strongly chromatically-stress regular. ◻

Proposition 13 indicates that despite the complexity of a corresponding chromatic polynomial of certain graphs, the results related to chromatically-stress regularity and chromatically-stress stability can be straightforward. In fact, Proposition 13 is valid for all geodetic graphs \(G\) for which \(diam(G) \leq 2\). A salient fact of Corollary 11 is that all complete \(m\)-partite graphs \(K_{n_1,n_2,\dots,n_m}\), \(n_i \geq 1\) \(\forall~i\), \(m \geq 2\), \(\chi(K_{n_1,n_2,\dots,n_m}) = m\) are chromatically-stress stable in respect of all \(\chi\)-colorings.
Exercise 1. Prove that a \(m\)-partite graph \(K_{n_1,n_2,\dots,n_m}\), \(n_i \geq 1\) \(\forall~i\), \(m \geq 2\), is chromatically-stress stable in respect of all \(\chi\)-colorings.
The intuitive complexity of this new graph variant can be illustrated by recalling that the chromatic polynomial of cycles is, \[\mathcal{P}_{C_n}(k, n) = (k – 1)^n + (-1)^n(k – 1).\] For odd cycles let \(k = 3\). Thus \(\mathcal{P}_{C_5}(3, 5)= 30\). Since, \(C_5\) is geodetic with \(diam(C_5) = 2\) the value of chromatic vertex-stress is easy to obtain. Clearly, for \(C_n\), \(n \geq 7\) the exhaustive enumeration to find say, lower and upper bounds is not very efficient. For an odd cycle \(C_n\), \(n \geq 7\) and without loss of generality, consider the following \(\chi\)-colorings.
Case 1. If \(n\) is odd, let \(\varphi_\chi^1:V(C_n) \mapsto \{c_1,c_2,c_3\}\) be: \(c(v_1) = c_1\), \(c(v_2) = c_2\), \(c(v_3) = c_1\), \(c(v_4) = c_2,\cdots,c(v_{n-1}) = c_2\) and \(c(v_n) = c_3\).
Case 2. If \(n = 3t_1\), \(t_1 \geq 3\) and \(t_1\) is odd, let \(\varphi_\chi^2:V(C_n) \mapsto \{c_1,c_2,c_3\}\) be: \(c(v_1) = c_1\), \(c(v_2) = c_2\), \(c(v_3) = c_3\), \(c(v_4) = c_1,\cdots,c(v_{n}) = c_3\).
Case 3. If \(n = 3t_2+ 2\), \(t_2 \geq 1\) and \(t_2\) is odd, let \(\varphi_\chi^3:V(C_n) \mapsto \{c_1,c_2,c_3\}\) be:
\(c(v_1) = c_1\), \(c(v_2) = c_2\), \(c(v_3) = c_3\), \(c(v_4) = c_1,\cdots,c(v_{n-2}) = c_3\) and \(c(v_{n-1}) = c_1\), \(c(v_n) = c_2\).
Case 4. If \(n = 3t_3+ 1\), \(t_3\geq 2\) and \(t_3\) is even, let \(\varphi_\chi^4:V(C_n) \mapsto \{c_1,c_2,c_3\}\) be:
\(c(v_1) = c_1\), \(c(v_2) = c_2\), \(c(v_3) = c_3\), \(c(v_4) = c_1,\cdots,c(v_{n-1}) = c_3\) and \(c(v_n) = c_2\).

Conjecture 14. An odd cycle \(C_n\), \(n\geq 7\) has: \[\mathcal{S}_{\varphi_\chi^1}(C_n) \leq \mathcal{S}_{\varphi_\chi}(C_n) \leq \mathcal{S}_{\varphi_\chi^2}(C_n)\] or \[\mathcal{S}_{\varphi_\chi^1}(C_n) \leq \mathcal{S}_{\varphi_\chi}(C_n) \leq \mathcal{S}_{\varphi_\chi^3}(C_n)\] or \[\mathcal{S}_{\varphi_\chi^1}(C_n) \leq \mathcal{S}_{\varphi_\chi}(C_n) \leq \mathcal{S}_{\varphi_\chi^4}(C_n).\]

Problem 1. Prove or disprove Conjecture 14.
The \(\chi\)-colorings which by conjecture yield the bounds in Conjecture 14 are called extremal chromatic stress colorings and for brevity, \(ECS\)-colorings. The concept of \(ECS\)-colorings in graphs offers a wide scope for further research.
Dedication: This paper is dedicated to the Founding Director of the Namibian Mathematics Institute, i.e. Stephanus Petrus Erwee. The dedication is inspired by the innovative project, Map Mathematics which covers a range of mathematics topics using maps of Namibia and Africa. This project is aimed at enhancing the teaching skills of senior mathematics teachers.

References

  1. Bondy, J. A., & Murty, U. S. R. (1976) . Graph Theory with Applications, Macmillan Press, London.

  2. Harary, F. (1969). Graph Theory, Addison-Wesley, Reading MA.

  3. Orendovici, R. (2011). Social Network Analysis and Simulation of the Development of Adversarial Networks.

  4. Shiny, J., & Ajitha, V. (2020). Stress regular graphs. Malaya Journal of Matematik, 8(3), 1152-1154.

  5. Kok, J., Shiny, J., & Ajitha, V. (2020). Total vertex stress alteration in cycle related graphs. Matematichki Bilten, 44(2), 149-162.

  6. Joseph, S. (2021). Induced stress of some graph operations. Malaya Journal of Matematik, 9(01), 259-261.

  7. Shiny, J., Kok, J., & Ajitha, V. (2021). Total induced vertex stress in barbell-like graphs. Journal of the Indonesian Mathematical Society, 27(2), 150-157.

  8. Adam, A. A. (1990). The chromatic polynomial of a graph, Ph.D. Thesis, University of the Witwatersrand.

  9. Srinivas, B. R., & Chaitanya, A. S. K. (2014). The chromatic polynomials and its algebraic properties. International Journal of Scientific and Innovative Mathematical Research (IJSIMR), 2(11), 914-922.