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.
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.
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.
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)\). ◻
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).\] ◻
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\).
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.
Bondy, J. A., & Murty, U. S. R. (1976) . Graph Theory with Applications, Macmillan Press, London.
Harary, F. (1969). Graph Theory, Addison-Wesley, Reading MA.
Orendovici, R. (2011). Social Network Analysis and Simulation of the Development of Adversarial Networks.
Shiny, J., & Ajitha, V. (2020). Stress regular graphs. Malaya Journal of Matematik, 8(3), 1152-1154.
Kok, J., Shiny, J., & Ajitha, V. (2020). Total vertex stress alteration in cycle related graphs. Matematichki Bilten, 44(2), 149-162.
Joseph, S. (2021). Induced stress of some graph operations. Malaya Journal of Matematik, 9(01), 259-261.
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.
Adam, A. A. (1990). The chromatic polynomial of a graph, Ph.D. Thesis, University of the Witwatersrand.
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.