Contents

Note: Certain bounds in respect of upper deg-centric graphs

Author(s): Johan Kok1
1Independent Mathematics Researcher, City of Tshwane, South Africa & Visiting 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 note presents some upper bounds for the size of the upper deg-centric grapg \(G_{ud}\) of a simple connected graph G. Amongst others, a result for graphs for which a compliant graph \(G\) has \(G_{ud} \cong \overline G\) is presented. Finally, results for size minimality in respect upper deg-centrication and minimum size of such graph \(G\) are presented.

Keywords: Upper deg-centric graph; upper deg-centrication; equi-eccentric graph.

1. Introduction

It is assumed that the reader is familiar with the basic notions and notation of graph theory. Where deemed necessary, useful definitions will be recalled from [1-3]. Only finite, undirected and connected simple graphs are considered. Furthermore, since the number of distinct connected graphs on \(n = 1, 2, 3\) vertices is respectively given by \(1, 1, 2\) this note will, unless stated otherwise, consider graphs of order \(n \geq 4\). Results for \(n = 1, 2, 3\) can easily be verified. Reference to vertices \(v_i,v_j\) will mean that \(v_i\) and \(v_j\) are distinct vertices. A classical graph from a graph \(G\) is its complement, \(\overline{G}\). The complement of a graph \(G\) can be defined in terms of a distance condition i.e. \(V(\overline{G}) = V(G)\) and \(E(\overline{G}) = \{v_iv_j:\) if and only if \(d_G(v_i,v_j) \neq 1\}\). Clearly, a generalized notion of a \(k\)-complement of graph \(G\) could be that for \(k \geq 1\) the \(k\)-complement of \(G\) is defined as a graph say, \(\overline{G}_{(k)}\) where, \(V(\overline{G}_{(k)}) = V(G)\) and \(E(\overline{G}_{(k)}) = \{v_iv_j: d_G(v_i,v_j) \neq k\}\). If a graphical parameter of a vertex such as its degree, eccentricity, coloring or alike is utilized in a relation condition to obtain a graph from a graph the study becomes interesting. Published studies with a distance condition in terms of the vertex eccentricity are found in [4,5]. With the world-wide interest in artificial intelligence, machine learning, deep data mining and alike, the notion of graphs from a graph may bring various futuristic applications to the fore. The era of evolving graphs has arrived.

2. Preliminaries

In a recently communicated paper the notion of upper degree-centrication has been introduced. This note has relevance to the upper deg-centric graph. See [6].

Definition 1. [6]Let \(G = (V(G), E(G))\) be a graph. Then the upper deg-centric graph of \(G\) denoted by, \(G_{ud}\) has vertices \(V(G_{ud}) = V(G)\) and \(E(G_{ud}) = \{v_iv_j: d_G(v_i,v_j) \geq deg_G(v_i)\}\).

Clearly, an edge \(v_iv_j \in E(G)\) and \(v_iv_j \in E(G_{ud})\) if and only if \(v_i\) or \(v_j\) is a pendant vertex in \(G\). Put differently, an edge \(v_iv_j \in E(G)\) and \(v_iv_j \in E(G_{ud})\) if and only if \(deg_G(v_i) = 1\) or \(deg_G(v_j) = 1\). Therefore, \(E(G_{ud}) \subseteq E(\overline G)\) if and only if \(\delta(G) \geq 2\).

Theorem 2. A \(2\)-regular graph \(G\) has \(G_{ud} \cong \overline G\).

Proof. Assume \(G\) is a \(2\)-regular graph. Thus \(deg_G(v_i) = 2\), \(\forall~v_i\). So \(N_{G_{ud}}(v_i) = V(G)\backslash N_G[v_i]\), \(\forall~i\) which implies that \(E(G_{ud}) = E(\overline G)\). Since \(V(G) = V(\overline G)\) it follows that \(G_{ud} \cong \overline G\). ◻

The converse of Theorem 2 does not hold. An example is the windmill graph \(Wd(k)\) which is obtained by joining \(k \geq 2\) copies of \(K_3\) at a shared central vertex. Clearly, the central vertex has degree equal to \(2k >2\) so \(Wd(k)\) is not \(2\)-regular. However, \(Wd(k)_{ud} \cong \overline{Wd(k)}\).

Theorem 3. A graph \(G\) has \(G_{ud} \cong \overline G\) if and only if \(V(G)\) can be partitioned into sets

\(X = \{v_j: deg_G(v_i) = 2\}\) and \(Y = V(G)\backslash X\)

such that the induced subgraph \(\langle Y\rangle\) is complete or empty.

Proof. For any vertex \(v_i \in V(G)\) the open neighborhood \(N_{G_{ud}}(v_i)\) can be partitioned into three sets that is:

(i) \(N^\rightarrow_{G_{ud}}(v_i) = \{v_j: deg_G(v_i) \leq d_G(v_i,v_j)\) and \(deg_G(v_j) > d_G(v_j,v_i)\}\).
(ii) \(N^\leftarrow_{G_{ud}}(v_i) = \{v_j: deg_G(v_i) > d_G(v_i,v_j)\) and \(deg_G(v_j) \leq d_G(v_j,v_i)\}\).
(iii) \(N^\leftrightarrow_{G_{ud}}(v_i) = \{v_j: deg_G(v_i) \leq d_G(v_i,v_j)\) and \(deg_G(v_j) \leq d_G(v_j,v_i)\}\).

Hence, (iii) represents the commutative initiation of edges.
Part 1: Assume that \(V(G)\) can be partitioned into sets

\(X = \{v_j: deg_G(v_i) = 2\}\) and \(Y = V(G)\backslash X\)

such that the induced subgraph \(\langle Y\rangle\) is complete or empty. From Definition 1 it is obvious that each \(v_i \in X\) initiates an edge to all vertices \(v_j\) if \(d_G(v_i,v_j) \geq 2\). All these edges are also obtained in \(\overline G\). Since each \(v_j \in Y\) has \(deg_G(v_j) \geq 3\) it cannot initiate all edges in accordance to the definition of \(\overline G\). Hence, for such \(v_j\) the iniation of an edge is prohibited. The aforesaid is in compliance because \(\langle Y\rangle\) is complete.
Part 2: Conversely, if \(G_{ud} \cong \overline G\) then possibly \(G\) is \(2\)-regular. In such case \(X = V(G)\) and \(Y = \emptyset\). Otherwise, any vertex \(v_i\) which yields an edge (or edges) in accordance with the definition of \(\overline G\) has \(deg_G(v_i) = 2\) by necessity. Hence a non-empty set \(X\) exists. If \(Y\) is non-empty then any \(v_j \in Y\) has \(deg_G(v_j) \geq 3\). A commutative initiated edge from \(v_j\) to \(v_i \in X\) is in order. However, an intiated edge amongst vertices in \(Y\) is prohibited. Such prohibition is only possible if \(\langle Y\rangle\) is complete. ◻

3. Bounds

Recall that the number of edges of a graph \(G\) is called the size of \(G\) and is denoted by, \(\varepsilon(G)\). From Theorem 2 a self-evident corollary follows.

Corollary 4. For \(G\) and \(\delta(G) \geq 2\) it follows that,

\(0 \leq \varepsilon(G_{ud}) \leq \frac{n(n-1)}{2} – \varepsilon(G) =\varepsilon(\overline{G})\).

There exists a finite number say, \(\gamma_n\) of distinct unlabeled trees on \(n\) vertices. The vertices of these distinct trees on \(n\) vertices may be labeled \(v_i\), \(i = 1,2,3,\dots,n\) in any fashion. Let these distinct and labeled trees be \(T_i\), \(1\leq i \leq \gamma_n\) such that:

\(\varepsilon(T_{1_{ud}}) \leq \varepsilon(T_{2_{ud}}) \leq \varepsilon(T_{3_{ud}}) \leq \cdots \leq \varepsilon(T_{\gamma_{n_{ud}}})\).

Lemma 5. Amongst all distinct trees \(T_i\), \(1 \leq i \leq \gamma_n\) the upper deg-centric graph of a path \(P_n\) and a star \(S_{1,n-1}\) has respectively, the minimum and maximum size, i.e.

\(\varepsilon(P_{n_{ud}}) \leq \varepsilon(T_{i_{ud}}) \leq \varepsilon(S_{{1,n-1}_{ud}})\).

Proof. The result follows from the fact that for a given \(n\) a path has minimum pendants and a star has maximum pendants read together with Definition 1. Indeed, \(S_{{1,n-1}_{ud}} \cong K_n\). ◻

Recall that \(G+e\) means the adding of an edge \(e\) to \(G\). If two or more edges say, \(e_1, e_2, e_3,\dots,e_k\) are added to \(G\) it is denoted by \(G+(e_1, e_2, e_3,\dots,e_k)\).

Lemma 6. For any tree \(T\) and \(G = T+e\) it follows that,

\(\varepsilon (G_{ud}) \leq \varepsilon(T_{ud})\).

Proof. The result follows from the fact that if \(e\) is added between vertices \(v_i, v_j\) then, \(deg_T(v_i) < deg_G(v_i)\) and \(deg_T(v_j) < deg_G(v_j)\). The aforesaid implies that for each vertes \(v_t\) for which \(d_T(v_i,v_t) = deg_T(v_i)\) at least the edge \(v_iv_t \in E(T_{ud})\) and \(v_iv_t \notin E(G_{ud})\). Similar argument follows in respect of vertex \(v_j\). Finally, certain distances between pairs of vertices may have decreased whilst none increased. This settles the result. ◻

To further this note Lemma 6 has been formulated specifically for trees. A similar result holds for graphs in general. We state it as an axiomatic corollary.

Corollary 7. For any graph \(G\) and \(H = G+e\) it follows that,

\(\varepsilon (H_{ud}) \leq \varepsilon(G_{ud})\).

It is known that any graph \(G\) has a finite number of distinct spanning trees. It is also known that a graph \(G\) can be reconstructed from any of its spanning trees by adding the required edges (or corresponding edges) needed.

Theorem 8. Let \(S\) be the set of distinct spanning trees of a graph \(G\). Then,

\(\varepsilon(G_{ud}) \leq \varepsilon(T^-_{ud})\) where, \(\varepsilon(T^-_{ud}) = min\{\varepsilon(T_{ud}):T \in S\}\).

Proof. Through immediate induction on the result of Lemma 6, it follows for any spanning tree \(T\) of \(G\) that, if \(H = T +(e_1, e_2, e_3,\dots,e_k)\) then \(\varepsilon(H_{ud}) \leq \varepsilon(T_{ud})\). Furthermore, amongst the finite number of distinct spanning trees of \(G\) there exists some \(T^-\) such that \(\varepsilon(T^-_{ud}) = min\{\varepsilon(T_{ud}):T \in S\}\). That settles the result. ◻

Recall that a graph \(G\) is traceable if \(G\) contains a Hamiltonian path.

Proposition 9. Let \(G\) be traceable then,

\(\varepsilon(G_{ud}) \leq \varepsilon(P_{n_{ud}}) = \frac{n^2-3n+6}{2}\).

Proof. Since \(G\) is traceable it contains a Hamilton path. Since \(\varepsilon(P_{n_{ud}}) \leq \varepsilon(T_{ud})\) where \(T\) is a tree of order \(n\) and read together with Theorem 8 the result follows. ◻

Proposition 10. Let \(G\) be Hamiltonian then,

\(\varepsilon(G_{ud}) \leq \varepsilon(C_{n_{ud}}) =\frac{n(n-3)}{2}\).

Proof. Since \(G\) is Hamiltonian it contains a Hamilton cycle. Since a result similar to Lemma 6 holds for cycles and \(\varepsilon(C_{n_{ud}}) = \frac{n(n-3)}{2} \leq \varepsilon(P_{n_{ud}})\), the result follows. ◻

Proposition 11. Let distinct graphs \(G\) and \(H\) both be of order \(n\).
(i) If \(G\) is a spanning subgraph of \(H\) then, \(\varepsilon(H_{ud}) \leq \varepsilon(G_{ud})\).
(ii) If \(G\) is not a spanning subgraph of \(H\) but \(G\) and \(H\) share a common spanning tree as well as \(\varepsilon(G) < \varepsilon(H)\) then, \(\varepsilon(H_{ud}) \leq \varepsilon(G_{ud})\).

Proof. (i) Clearly, the result in Corollary 7 can be applied by iteratively adding appropriate edges to \(G\) one at a time to obtain \(H\). For each iteration Corollary 7 remains valid. That settles the result.
(ii) Clearly, the result in Lemma 6 can be applied by iteratively adding appropriate edges to two copies of a common spanning \(T\) of \(G\) and \(H\), one at a time to first obtain \(G\) and thereafter obtain \(G\). For each iteration Lemma 6 remains valid. That settles the result. ◻

4. Minimum graph size

For \(n = 1,3,4\) it is easy to verify that the only graphs \(G\) for which \(G_{ud} = \mathfrak{N}_n\) (alternatively, \(G_{ud} = \overline{K}_n\)) are the corresponding complete graphs. The graph \(K_2\) is excluded because \(K_{2_{ud}} = K_2\). It is obvious that for \(n \geq 5\) there exists a non-complete graph \(G\) with minimum size such that \(G_{ud} = \mathfrak{N}_n\). If \(G_{ud} = \mathfrak{N}_n\) and for any edge \(e\) the upper deg-centric graph of \(G-e\) is not empty then \(G\) is said to be a minimal graph in respect of upper deg-centrication. For a given \(n \geq 5\) let the set of all minimal graphs in respect of upper deg-centrication be \(\mathcal{G}(n)\). A graph of order \(n\) and of minimum size such that \(G_{ud} = \mathfrak{N}_n\) is a graph \(G \in \mathcal{G}(n)\) for which \(\varepsilon(G) = \min\{\varepsilon(H): H \in \mathcal{G}(n)\}\). Clearly, such \(G\) cannot have an pendant vertex. Hence, for minimality of \(G\) such that \(G_{ud} = \mathfrak{N}_n\) the graph \(G\) must have \(diam(G) = 2\) and \(\delta(G) = 3\). For a graph \(G\) of order \(n = 5\) which has \(diam(G) = 2\) and has \(\delta(G) = 3\) it must have \(\varepsilon(G) \geq 8\). Hence, if \(\varepsilon(G) = 8\) it represents the minimum size of a graph \(G\) of order \(5\) such that \(G_{ud} \cong \mathfrak{N}_5\). The chorded cycle \(C_5 + (v_1v_3,v_1v_4, v_2v_5)\) complies. For a graph \(G\) of order \(n = 6\) which is \(2\)-equi-eccentric (hence, \(diam(G) = 2\)) and has \(\delta(G) = 3\) it must have \(\varepsilon(G) \geq 9\). Hence, if \(\varepsilon(G) = 9\) it represents the minimum size of a graph \(G\) of order \(6\) such that \(G_{ud} \cong \mathfrak{N}_6\). The chorded cycle \(C_6 + (v_1v_4, v_2v_5, v_3v_6)\) complies. It is known that the Petersen graph denoted by, \(\mathcal{P}\) is both \(3\)-regular and \(2\)-equi-eccentric. Hence \(\varepsilon(\mathcal{P}) = 15\) represents the minimum size of a graph \(G\) of order \(10\) such that \(G_{ud} = \mathfrak{N}_{10}\). We are left to consider graphs of order \(n \geq 7\), \(n \neq 10\).
In [1] a graph \(G_n = K_m \circ K_1 \bigoplus K_1\), \(m \geq 1\) and \(n = 2m + 1\) is defined as:
(i) Construct the corona graph \(K_m \circ K_1\) and label the vertices of \(K_m\) as \(v_1,v_2,v_3,\dots,\\ v_m\) and the \(m\)-copies of \(K_1\) vertices as \(u_1,u_2,u_3,\dots,u_m\) and thereafter,
(ii) Join an addition vertex \(w_1\) as a common neighbor to all vertices \(u_i\), \(1 \leq i \leq m\).
From Theorem 3 in [1] it is known that such graph \(G_n\) is a minimal \(2\)-equi-eccentric graph hence, \(diam(G_n) = 2\). Note that this construction yields graphs of odd order. Furthermore, for \(n\) is odd the size of \(G_n\) is a quadratic function of \(m\) where, \(m = \frac{n-1}{2}\).
Our first step is to search for graphs which are minimal in respect of \(2\)-equi-eccentricity and have minimum size. Thereafter the minimum number of edges must be added to obtain graphs \(G\) of minimum size such that \(\delta(G) = 3\). In [1] the base graphs \(K_2\) and \(K_3\) were used to construct a graph for a given \(n \geq 7\), \(n \neq 10\) (our lower bound) by:
(i) Take base graph \(K_2\) or \(K_3\) on vertices \(v_1, v_2\) or \(v_1, v_2, v_3\) respectively.
(ii) Take \(t = n-3\) (for \(K_2\)) or \(t = n-4\) (for \(K_3\)) isolated vertices \(u_i\), \(1 \leq i \leq t,(n-3\) or \(n-4)\) and attach \(q_1, q_2\) or \(q_1, q_2, q_3\), where \(q_i \geq 2\) as pendants to the corresponding \(v_1, v_2\) or \(v_1, v_2, v_3\) where \(q_1+q_2 = n-3\) or \(q_1+q_2+q_3 = n-4\).
(iii) Take an isolated vertex \(w_1\) and add the edges \(u_iw_1\), \(\forall~i\) so that \(w_1\) serves as a common neighbor.
It is known that both graphs obtained above are \(2\)-equi-eccentric and of minimum size. See Theorem 7 in [1]. Note that in both cases the size is given by \(2(n-3)+1 = 2n-5\) or \(2(n-4) +3 = 2n-5\). Observe that if \(K_1\) is used as a base graph the size is \(2n-4\) and \(2n-4 > 2n-5\). Label any of these graphs as \(M^2_n\) (for base graph \(K_2\)) and \(M^3_n\) (for base graph \(K_3\)). By excluding \(n = 10\) and adding the minimum additional edges \(u_1u_2, u_3u_4, \dots,u_{t-1}u_{t}\) the graphs \(M^{2+}_n\), \(M^{3+}_n\) can be obtained. The aforesaid is always possible by selecting the base graph either \(K_2\) or \(K_3\). Clearly, both \(M^{2+}_n\), \(M^{3+}_n\) are of minimum size, \(2\)-equi-eccentric with \(\delta(M^{2+}_n) = \delta(M^{3+}_n) = 3\). Hence, \(M^{2+}_{n_{ud}}= M^{3+}_{n_{ud}} = \mathfrak{N}_n\). We state a theorem.

Theorem 12. A graph of order \(n = 10\) and of minimum size, has \(G_{ud} = \mathfrak{N}_n\) if and only if \(G = \mathcal{P}\), (the Petersen graph).

Proof. Firstly, that \(\mathcal{P}_{ud} = \mathfrak{N}_{10}\) follows from Definition 1. Since each vertex in the Petersen graph has degree equal to \(3\) and \(diam(\mathcal{P}) = 2\) the size is a minimum. Conversely, the fact that both \(\varepsilon(M^{2+}_{10}) > 15\) and \(\varepsilon(M^{3+}_{10}) > 15\) whereas, \(\varepsilon(\mathcal{P}) = 15\) settles the result. ◻

Theorem 13. A graph \(G\) of order \(n \geq 7\), \(n \neq 10\) and of minimum size such that \(G_{ud} = \mathfrak{N}_n\) has,

\(\varepsilon(G) = (2n-5) + \lceil \frac{n-4}{2}\rceil\).

Proof. Clearly, a graph \(G\) of order \(n \geq 7\) and of minimum size such that \(G_{ud} = \mathfrak{N}_n\) has \(\varepsilon(G) = min\{\varepsilon(M^{2+}_n), \varepsilon(M^{3+}_n)\}\). It is known that \(\varepsilon(M^2_n) = \varepsilon(M^3_n) = 2n-5\) and a minimum size. Furthermore, from the definition of the upper ceiling function it follows that \(\lceil \frac{n-4}{2}\rceil = x\) implies that, \(\frac{n-4}{2} < x \leq \frac{n-4}{2}\) and \(\lceil \frac{n-3}{2}\rceil = y\) implies that, \(\frac{n-3}{2} < y \leq \frac{n-3}{2}\). Furthermore, \(y \geq x\). Hence, \((2n-5) + x \leq (2n-5) + y\). It means that the minimum size is given by \(\varepsilon(M^{3+}_n) = (2n-5) + \lceil \frac{n-4}{2}\rceil\). The ceiling function is required because of the dependency on \(n-4\) is odd or even. ◻

5. Conclusion

The note concludes with a conjecture.

Conjecture 1. Consider distinct graphs \(G\) and \(H\). If \(\varepsilon(G) < \varepsilon(H)\) then, \(\varepsilon(H_{ud}) \leq \varepsilon(G_{ud})\).

Dedication: This paper is dedicated to late Theresa Bernadette Kok (n\(\acute{e}\)e Tomlinson) in acknowledgement of; and with deep gratitude for the profound influence she had on the author’s endeavors to become a research mathematician.

R.I.P. Spokie.

Acknowledgement

The author would like to thank the anonymous referees for their constructive comments.

Conflict of interest:

The author declares there is no conflict of interest in respect of this research.

References

  1. Akiyama, J., Ando, K., & Avis, D. (1984). Miscellaneous properties of equi-eccentric graphs. Annals of Discrete Mathematics, 20, 13-23.
  2. Bondy, J. A., & Murty, U. S. R. (1976). Graph Theory with Applications. London: Macmillan Press.
  3. Harary, F. (1969). Graph Theory. Reading, MA: Addison-Wesley.
  4. Raja, M. R., Mangam, T. A., & Naduvath, S. (2022). Eccentric completion of a graph. Communications in Combinatorics and Optimization, 7(2), 193-201.
  5. Raja, M. R., Kok, J., Mangam, T. A., & Naduvath, S. (2023). Cyclic property of iterative eccentrication of a graph. Discrete Mathematics, Algorithms and Applications, 15(7), 2250155(1-13).
  6. Thalavayalil, T. T., Kok, J., & Naduvath, S. A study on upper deg-centric graphs. (Communicated).