Total and forcing total edge-to-vertex monophonic number of a graph

For a connected graph \(G = \left( V,E\right) \), a set \(S\subseteq E(G)\) is called a total edge-to-vertex monophonic set of a connected graph G if the subgraph induced by S has no isolated edges. The total edge-to-vertex monophonic number \(m_{tev}(G)\) of G is the minimum cardinality of its total edge-to-vertex monophonic set of G. The total edge-to-vertex monophonic number of certain classes of graphs is determined and some of its general properties are studied. Connected graphs of size \(q \ge 3 \) with total edge-to-vertex monophonic number q is characterized. It is shown that for positive integers \(r_{m},d_{m}\) and \(l\ge 4\) with \(r_{m}< d_{m} \le 2 r_{m}\), there exists a connected graph G with \(\textit{rad}_ {m} G = r_{m}\), \(\textit{diam}_ {m} G = d_{m}\) and \(m_{tev}(G) = l\) and also shown that for every integers a and b with \(2 \le a \le b\), there exists a connected graph G such that \( m_{ev}\left( G\right) = b\) and \(m_{tev}(G) = a + b\). A forcing subset for S of minimum cardinality is a minimum forcing subset of S. The forcing total edge-to-vertex monophonic number of S, denoted by \(f_{tev}(S)\) is the cardinality of a minimum forcing subset of S. The forcing total edge-to-vertex monophonic number of G, denoted by \(f_{tev}(G) = \textit{min}\{f_{tev}(S)\}\), where the minimum is taken over all total edge-to-vertex monophonic set S in G. The forcing total edge-to-vertex monophonic number of certain classes of graphs are determined and some of its general properties are studied. It is shown that for every integers a and b with \(0 \le a \le b\) and \(b \ge 2\), there exists a connected graph G such that \(f_{tev}(G) = a\) and \( m _{tev}(G) = b\), where \( f _{tev}(G)\) is the forcing total edge-to-vertex monophonic number of G.     

The (vertex-)monochromatic index of a graph

A tree T in an edge-colored (vertex-colored) graph H is called a monochromatic (vertex-monochromatic) tree if all the edges (internal vertices) of T have the same color. For \(S\subseteq V(H)\), a monochromatic (vertex-monochromatic) S-tree in H is a monochromatic (vertex-monochromatic) tree of H containing the vertices of S. For a connected graph G and a given integer k with \(2\le k\le |V(G)|\), the k -monochromatic index \(mx_k(G)\) (k -monochromatic vertex-index \(mvx_k(G)\)) of G is the maximum number of colors needed such that for each subset \(S\subseteq V(G)\) of k vertices, there exists a monochromatic (vertex-monochromatic) S-tree. For \(k=2\), Caro and Yuster showed that \(mc(G)=mx_2(G)=|E(G)|-|V(G)|+2\) for many graphs, but it is not true in general. In this paper, we show that for \(k\ge 3\), \(mx_k(G)=|E(G)|-|V(G)|+2\) holds for any connected graph G, completely determining the value. However, for the vertex-version \(mvx_k(G)\) things will change tremendously. We show that for a given connected graph G, and a positive integer L with \(L\le |V(G)|\), to decide whether \(mvx_k(G)\ge L\) is NP-complete for each integer k such that \(2\le k\le |V(G)|\). Finally, we obtain some Nordhaus–Gaddum-type results for the k-monochromatic vertex-index.     

On the difference of two generalized connectivities of a graph

The concept of k-connectivity \(\kappa '_{k}(G)\) of a graph G, introduced by Chartrand in 1984, is a generalization of the cut-version of the classical connectivity. Another generalized connectivity of a graph G, named the generalized k-connectivity \(\kappa _{k}(G)\), mentioned by Hager in 1985, is a natural generalization of the path-version of the classical connectivity. In this paper, we get the lower and upper bounds for the difference of these two parameters by showing that for a connected graph G of order n, if \(\kappa '_k(G)\ne n-k+1\) where \(k\ge 3\), then \(0\le \kappa '_k(G)-\kappa _k(G)\le n-k-1\); otherwise, \(-\lfloor \frac{k}{2}\rfloor +1\le \kappa '_k(G)-\kappa _k(G)\le n-k\). Moreover, all of these bounds are sharp. Some specific study is focused for the case \(k=3\). As results, we characterize the graphs with \(\kappa '_3(G)=\kappa _3(G)=t\) for \(t\in \{1, n-3, n-2\}\), and give a necessary condition for \(\kappa '_3(G)=\kappa _3(G)\) by showing that for a connected graph G of order n and size m, if \(\kappa '_3(G)=\kappa _3(G)=t\) where \(1\le t\le n-3\), then \(m\le {n-2\atopwithdelims ()2}+2t\). Moreover, the unique extremal graph is given for the equality to hold.     

Improved upper bound for the degenerate and star chromatic numbers of graphs

Let \(G=G(V,E)\) be a graph. A proper coloring of G is a function \(f:V\rightarrow N\) such that \(f(x)\ne f(y)\) for every edge \(xy\in E\). A proper coloring of a graph G such that for every \(k\ge 1\), the union of any k color classes induces a \((k-1)\)-degenerate subgraph is called a degenerate coloring; a proper coloring of a graph with no two-colored \(P_{4}\) is called a star coloring. If a coloring is both degenerate and star, then we call it a degenerate star coloring of graph. The corresponding chromatic number is denoted as \(\chi _{sd}(G)\). In this paper, we employ entropy compression method to obtain a new upper bound \(\chi _{sd}(G)\le \lceil \frac{19}{6}\Delta ^{\frac{3}{2}}+5\Delta \rceil \) for general graph G.     

The $$(k,\ell )$$-proper index of graphs

A tree T in an edge-colored graph is called a proper tree if no two adjacent edges of T receive the same color. Let G be a connected graph of order n and k be an integer with \(2\le k \le n\). For \(S\subseteq V(G)\) and \(|S| \ge 2\), an S-tree is a tree containing the vertices of S in G. A set \(\{T_1,T_2,\ldots ,T_\ell \}\) of S-trees is called internally disjoint if \(E(T_i)\cap E(T_j)=\emptyset \) and \(V(T_i)\cap V(T_j)=S\) for \(1\le i\ne j\le \ell \). For a set S of k vertices of G, the maximum number of internally disjoint S-trees in G is denoted by \(\kappa (S)\). The k-connectivity \(\kappa _k(G)\) of G is defined by \(\kappa _k(G)=\min \{\kappa (S)\mid S\) is a k-subset of \(V(G)\}\). For a connected graph G of order n and for two integers k and \(\ell \) with \(2\le k\le n\) and \(1\le \ell \le \kappa _k(G)\), the \((k,\ell )\)-proper index \(px_{k,\ell }(G)\) of G is the minimum number of colors that are required in an edge-coloring of G such that for every k-subset S of V(G), there exist \(\ell \) internally disjoint proper S-trees connecting them. In this paper, we show that for every pair of positive integers k and \(\ell \) with \(k \ge 3\) and \(\ell \le \kappa _k(K_{n,n})\), there exists a positive integer \(N_1=N_1(k,\ell )\) such that \(px_{k,\ell }(K_n) = 2\) for every integer \(n \ge N_1\), and there exists also a positive integer \(N_2=N_2(k,\ell )\) such that \(px_{k,\ell }(K_{m,n}) = 2\) for every integer \(n \ge N_2\) and \(m=O(n^r) (r \ge 1)\). In addition, we show that for every \(p \ge c\root k \of {\frac{\log _a n}{n}}\) (\(c \ge 5\)), \(px_{k,\ell }(G_{n,p})\le 2\) holds almost surely, where \(G_{n,p}\) is the Erd?s–Rényi random graph model.     

A new graph parameter and a construction of larger graph without increasing radio <Emphasis Type="Italic">k</Emphasis>-chromatic number

For a positive integer \(k\ge 2\), the radio k-coloring problem is an assignment L of non-negative integers (colors) to the vertices of a finite simple graph G satisfying the condition \(|L(u)-L(v)| \ge k+1-d(u,v)\), for any two distinct vertices u, v of G and d(u, v) being distance between u, v. The span of L is the largest integer assigned by L, while 0 is taken as the smallest color. An \(rc_k\)-coloring on G is a radio k-coloring on G of minimum span which is referred as the radio k-chromatic number of G and denoted by \(rc_k(G)\). An integer h, \(0<h<rc_k(G)\), is a hole in a \(rc_k\)-coloring on G if h is not assigned by it. In this paper, we construct a larger graph from a graph of a certain class by using a combinatorial property associated with \((k-1)\) consecutive holes in any \(rc_k\)-coloring of a graph. Exploiting the same property, we introduce a new graph parameter, referred as \((k-1)\)-hole index of G and denoted by \(\rho _k(G)\). We also explore several properties of \(\rho _k(G)\) including its upper bound and relation with the path covering number of the complement \(G^c\).     

Neighbor sum distinguishing total coloring of graphs with bounded treewidth

A proper total k-coloring \(\phi \) of a graph G is a mapping from \(V(G)\cup E(G)\) to \(\{1,2,\dots , k\}\) such that no adjacent or incident elements in \(V(G)\cup E(G)\) receive the same color. Let \(m_{\phi }(v)\) denote the sum of the colors on the edges incident with the vertex v and the color on v. A proper total k-coloring of G is called neighbor sum distinguishing if \(m_{\phi }(u)\not =m_{\phi }(v)\) for each edge \(uv\in E(G).\) Let \(\chi _{\Sigma }^t(G)\) be the neighbor sum distinguishing total chromatic number of a graph G. Pil?niak and Wo?niak conjectured that for any graph G, \(\chi _{\Sigma }^t(G)\le \Delta (G)+3\). In this paper, we show that if G is a graph with treewidth \(\ell \ge 3\) and \(\Delta (G)\ge 2\ell +3\), then \(\chi _{\Sigma }^t(G)\le \Delta (G)+\ell -1\). This upper bound confirms the conjecture for graphs with treewidth 3 and 4. Furthermore, when \(\ell =3\) and \(\Delta \ge 9\), we show that \(\Delta (G) + 1\le \chi _{\Sigma }^t(G)\le \Delta (G)+2\) and characterize graphs with equalities.     

Convex median and anti-median at prescribed distance

The status of a vertex v in a connected graph G is the sum of the distances between v and all the other vertices of G. The subgraph induced by the vertices of minimum (maximum) status in G is called median (anti-median) of G. Let \(H=(G_1,G_2,r)\) denote a graph with \(G_1\) as the median and \(G_2\) as the anti-median of H, \(d(G_1,G_2)=r\) and both \(G_1\) and \(G_2\) are convex subgraphs of H. It is known that \((G_1,G_2,r)\) exists for every \(G_1\), \(G_2\) with \(r \ge \left\lfloor diam(G_1)/2\right\rfloor +\left\lfloor diam(G_2)/2\right\rfloor +2\). In this paper we show the existence of \((G_1,G_2,r)\) for every \(G_1\), \(G_2\) and \(r \ge 1\). We also obtain a sharp upper bound for the maximum status difference in a graph G.     

Neighbor sum distinguishing total coloring of 2-degenerate graphs

A proper k-total coloring of a graph G is a mapping from \(V(G)\cup E(G)\) to \(\{1,2,\ldots ,k\}\) such that no two adjacent or incident elements in \(V(G)\cup E(G)\) receive the same color. Let f(v) denote the sum of the colors on the edges incident with v and the color on vertex v. A proper k-total coloring of G is called neighbor sum distinguishing if \(f(u)\ne f(v)\) for each edge \(uv\in E(G)\). Let \(\chi ''_{\Sigma }(G)\) denote the smallest integer k in such a coloring of G. Pil?niak and Wo?niak conjectured that for any graph G, \(\chi ''_{\Sigma }(G)\le \Delta (G)+3\). In this paper, we show that if G is a 2-degenerate graph, then \(\chi ''_{\Sigma }(G)\le \Delta (G)+3\); Moreover, if \(\Delta (G)\ge 5\) then \(\chi ''_{\Sigma }(G)\le \Delta (G)+2\).     

Sparse multipartite graphs as partition universal for graphs with bounded degree

For graphs G and H, let \(G\rightarrow (H,H)\) signify that any red/blue edge coloring of G contains a monochromatic H as a subgraph. Denote \(\mathcal {H}(\Delta ,n)=\{H:|V(H)|=n,\Delta (H)\le \Delta \}\). For any \(\Delta \) and n, we say that G is partition universal for \(\mathcal {H}(\Delta ,n)\) if \(G\rightarrow (H,H)\) for every \(H\in \mathcal {H}(\Delta ,n)\). Let \(G_r(N,p)\) be the random spanning subgraph of the complete r-partite graph \(K_r(N)\) with N vertices in each part, in which each edge of \(K_r(N)\) appears with probability p independently and randomly. We prove that for fixed \(\Delta \ge 2\) there exist constants r, B and C depending only on \(\Delta \) such that if \(N\ge Bn\) and \(p=C(\log N/N)^{1/\Delta }\), then asymptotically almost surely \(G_r(N,p)\) is partition universal for \(\mathcal {H}(\Delta ,n)\).     

Majorization and the spectral radius of starlike trees

A starlike tree is a tree with exactly one vertex of degree greater than two. The spectral radius of a graph G, that is denoted by \(\lambda (G)\), is the largest eigenvalue of G. Let k and \(n_1,\ldots ,n_k\) be some positive integers. Let \(T(n_1,\ldots ,n_k)\) be the tree T (T is a path or a starlike tree) such that T has a vertex v so that \(T{\setminus } v\) is the disjoint union of the paths \(P_{n_1-1},\ldots ,P_{n_k-1}\) where every neighbor of v in T has degree one or two. Let \(P=(p_1,\ldots ,p_k)\) and \(Q=(q_1,\ldots ,q_k)\), where \(p_1\ge \cdots \ge p_k\ge 1\) and \(q_1\ge \cdots \ge q_k\ge 1\) are integer. We say P majorizes Q and let \(P\succeq _M Q\), if for every j, \(1\le j\le k\), \(\sum _{i=1}^{j}p_i\ge \sum _{i=1}^{j}q_i\), with equality if \(j=k\). In this paper we show that if P majorizes Q, that is \((p_1,\ldots ,p_k)\succeq _M(q_1,\ldots ,q_k)\), then \(\lambda (T(q_1,\ldots ,q_k))\ge \lambda (T(p_1,\ldots ,p_k))\).     

Neighbor sum distinguishing list total coloring of subcubic graphs

Let \(G=(V, E)\) be a simple graph and denote the set of edges incident to a vertex v by E(v). The neighbor sum distinguishing (NSD) total choice number of G, denoted by \(\mathrm{ch}_{\Sigma }^{t}(G)\), is the smallest integer k such that, after assigning each \(z\in V\cup E\) a set L(z) of k real numbers, G has a total coloring \(\phi \) satisfying \(\phi (z)\in L(z)\) for each \(z\in V\cup E\) and \(\sum _{z\in E(u)\cup \{u\}}\phi (z)\ne \sum _{z\in E(v)\cup \{v\}}\phi (z)\) for each \(uv\in E\). In this paper, we propose some reducible configurations of NSD list total coloring for general graphs by applying the Combinatorial Nullstellensatz. As an application, we present that \(\mathrm{ch}^{t}_{\Sigma }(G)\le \Delta (G)+3\) for every subcubic graph G.     

Neighbor sum distinguishing total coloring of planar graphs without 4-cycles

Let \(G=(V,E)\) be a graph and \(\phi : V\cup E\rightarrow \{1,2,\ldots ,k\}\) be a proper total coloring of G. Let f(v) denote the sum of the color on a vertex v and the colors on all the edges incident with v. The coloring \(\phi \) is neighbor sum distinguishing if \(f(u)\ne f(v)\) for each edge \(uv\in E(G)\). The smallest integer k in such a coloring of G is the neighbor sum distinguishing total chromatic number of G, denoted by \(\chi _{\Sigma }''(G)\). Pil?niak and Wo?niak conjectured that \(\chi _{\Sigma }''(G)\le \Delta (G)+3\) for any simple graph. By using the famous Combinatorial Nullstellensatz, we prove that \(\chi _{\Sigma }''(G)\le \max \{\Delta (G)+2, 10\}\) for planar graph G without 4-cycles. The bound \(\Delta (G)+2\) is sharp if \(\Delta (G)\ge 8\).     

Neighbor product distinguishing total colorings

A total-[k]-coloring of a graph G is a mapping \(\phi : V (G) \cup E(G)\rightarrow \{1, 2, \ldots , k\}\) such that any two adjacent elements in \(V (G) \cup E(G)\) receive different colors. Let f(v) denote the product of the color of a vertex v and the colors of all edges incident to v. A total-[k]-neighbor product distinguishing-coloring of G is a total-[k]-coloring of G such that \(f(u)\ne f(v)\), where \(uv\in E(G)\). By \(\chi ^{\prime \prime }_{\prod }(G)\), we denote the smallest value k in such a coloring of G. We conjecture that \(\chi _{\prod }^{\prime \prime }(G)\le \Delta (G)+3\) for any simple graph with maximum degree \(\Delta (G)\). In this paper, we prove that the conjecture holds for complete graphs, cycles, trees, bipartite graphs and subcubic graphs. Furthermore, we show that if G is a \(K_4\)-minor free graph with \(\Delta (G)\ge 4\), then \(\chi _{\prod }^{\prime \prime }(G)\le \Delta (G)+2\).     

On the algorithmic aspects of strong subcoloring

A partition of the vertex set V(G) of a graph G into \(V(G)=V_1\cup V_2\cup \cdots \cup V_k\) is called a k-strong subcoloring if \(d(x,y)\ne 2\) in G for every \(x,y\in V_i\), \(1\le i \le k\) where d(x, y) denotes the length of a shortest x-y path in G. The strong subchromatic number is defined as \(\chi _{sc}(G)=\text {min}\{ k:G \text { admits a }k\)-\(\text {strong subcoloring}\}\). In this paper, we explore the complexity status of the StrongSubcoloring problem: for a given graph G and a positive integer k, StrongSubcoloring is to decide whether G admits a k-strong subcoloring. We prove that StrongSubcoloring is NP-complete for subcubic bipartite graphs and the problem is polynomial time solvable for trees. In addition, we prove the following dichotomy results: (i) for the class of \(K_{1,r}\)-free split graphs, StrongSubcoloring is in P when \(r\le 3\) and NP-complete when \(r>3\) and (ii) for the class of H-free graphs, StrongSubcoloring is polynomial time solvable only if H is an induced subgraph of \(P_4\); otherwise the problem is NP-complete. Next, we consider a lower bound on the strong subchromatic number. A strong set is a set S of vertices of a graph G such that for every \(x,y\in S\), \(d(x,y)= 2\) in G and the cardinality of a maximum strong set in G is denoted by \(\alpha _{s}(G)\). Clearly, \(\alpha _{s}(G)\le \chi _{sc}(G)\). We consider the complexity status of the StrongSet problem: given a graph G and a positive integer k, StrongSet asks whether G contains a strong set of cardinality k. We prove that StrongSet is NP-complete for (i) bipartite graphs and (ii) \(K_{1,4}\)-free split graphs, and it is polynomial time solvable for (i) trees and (ii) \(P_4\)-free graphs.     

Upper bounds of proper connection number of graphs

A total weighting of a graph G is a mapping \(\phi \) that assigns a weight to each vertex and each edge of G. The vertex-sum of \(v \in V(G)\) with respect to \(\phi \) is \(S_{\phi }(v)=\sum _{e\in E(v)}\phi (e)+\phi (v)\). A total weighting is proper if adjacent vertices have distinct vertex-sums. A graph \(G=(V,E)\) is called \((k,k')\)-choosable if the following is true: If each vertex x is assigned a set L(x) of k real numbers, and each edge e is assigned a set L(e) of \(k'\) real numbers, then there is a proper total weighting \(\phi \) with \(\phi (y)\in L(y)\) for any \(y \in V \cup E\). In this paper, we prove that for any graph \(G\ne K_1\), the Mycielski graph of G is (1,4)-choosable. Moreover, we give some sufficient conditions for the Mycielski graph of G to be (1,3)-choosable. In particular, our result implies that if G is a complete bipartite graph, a complete graph, a tree, a subcubic graph, a fan, a wheel, a Halin graph, or a grid, then the Mycielski graph of G is (1,3)-choosable.     

The capture time of a planar graph

This paper examines the capture time of a planar graph in a variant of the pursuit-evasion games, called cops and robbers game. Since any planar graph is 3-cop-win, we study the capture time of a planar graph G of n vertices using three cops, which is denoted by \(capt_3(G)\). We present a new capture strategy and show that \(capt_3(G) \le 2n\). This is the first result on \(capt_3(G)\).     

Planar graphs without chordal 5-cycles are 2-good

Let G be a connected graph with \(n\ge 2\) vertices. Suppose that a fire breaks out at a vertex v of G. A firefighter starts to protect vertices. At each step, the firefighter protects two vertices not yet on fire. At the end of each step, the fire spreads to all the unprotected vertices that have a neighbour on fire. Let sn\(_2(v)\) denote the maximum number of vertices in G that the firefighter can save when a fire breaks out at vertex v. The 2-surviving rate \(\rho _2(G)\) of G is defined to be the real number \(\frac{1}{n^2} \sum _{v\in V(G)} \mathrm{sn}_2(v)\). Then it is obvious that \(0<\rho _2(G)<1\). The graph G is called 2-good if there is a constant \(c>0\) such that \(\rho _2(G)>c\). In this paper, we prove that every planar graph with \(n\ge 2\) vertices and without chordal 5-cycles is 2-good.     

The adjacent vertex distinguishing total chromatic numbers of planar graphs with $$\Delta =10$$

A (proper) total-k-coloring of a graph G is a mapping \(\phi : V (G) \cup E(G)\mapsto \{1, 2, \ldots , k\}\) such that any two adjacent elements in \(V (G) \cup E(G)\) receive different colors. Let C(v) denote the set of the color of a vertex v and the colors of all incident edges of v. A total-k-adjacent vertex distinguishing-coloring of G is a total-k-coloring of G such that for each edge \(uv\in E(G)\), \(C(u)\ne C(v)\). We denote the smallest value k in such a coloring of G by \(\chi ''_{a}(G)\). It is known that \(\chi _{a}''(G)\le \Delta (G)+3\) for any planar graph with \(\Delta (G)\ge 11\). In this paper, we show that if G is a planar graph with \(\Delta (G)\ge 10\), then \(\chi _{a}''(G)\le \Delta (G)+3\). Our approach is based on Combinatorial Nullstellensatz and the discharging method.     

More bounds for the Grundy number of graphs

A coloring of a graph \(G=(V,E)\) is a partition \(\{V_1, V_2, \ldots , V_k\}\) of V into independent sets or color classes. A vertex \(v\in V_i\) is a Grundy vertex if it is adjacent to at least one vertex in each color class \(V_j\) for every \(j<i\). A coloring is a Grundy coloring if every vertex is a Grundy vertex, and the Grundy number \(\Gamma (G)\) of a graph G is the maximum number of colors in a Grundy coloring. We provide two new upper bounds on Grundy number of a graph and a stronger version of the well-known Nordhaus-Gaddum theorem. In addition, we give a new characterization for a \(\{P_{4}, C_4\}\)-free graph by supporting a conjecture of Zaker, which says that \(\Gamma (G)\ge \delta (G)+1\) for any \(C_4\)-free graph G.