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.
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.
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. ◻
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. ◻
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. ◻
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.
The author declares there is no conflict of interest in respect of this research.