Weak {2}-domination number of Cartesian products of cycles

For a graph \(G=(V, E)\), a weak \(\{2\}\)-dominating function \(f:V\rightarrow \{0,1,2\}\) has the property that \(\sum _{u\in N(v)}f(u)\ge 2\) for every vertex \(v\in V\) with \(f(v)= 0\), where N(v) is the set of neighbors of v in G. The weight of a weak \(\{2\}\)-dominating function f is the sum \(\sum _{v\in V}f(v)\) and the minimum weight of a weak \(\{2\}\)-dominating function is the weak \(\{2\}\)-domination number. In this paper, we introduce a discharging approach and provide a short proof for the lower bound of the weak \(\{2\}\)-domination number of \(C_n \Box C_5\), which was obtained by St?pień, et al. (Discrete Appl Math 170:113–116, 2014). Moreover, we obtain the weak \(\{2\}\)-domination numbers of \(C_n \Box C_3\) and \(C_n \Box C_4\).     

Paired-domination number of claw-free odd-regular graphs

A paired-dominating set of a graph G is a dominating set of vertices whose induced subgraph has a perfect matching, while the paired-domination number is the minimum cardinality of a paired-dominating set in the graph, denoted by \(\gamma _{pr}(G)\). Let G be a connected \(\{K_{1,3}, K_{4}-e\}\)-free cubic graph of order n. We show that \(\gamma _{pr}(G)\le \frac{10n+6}{27}\) if G is \(C_{4}\)-free and that \(\gamma _{pr}(G)\le \frac{n}{3}+\frac{n+6}{9(\lceil \frac{3}{4}(g_o+1)\rceil +1)}\) if G is \(\{C_{4}, C_{6}, C_{10}, \ldots , C_{2g_o}\}\)-free for an odd integer \(g_o\ge 3\); the extremal graphs are characterized; we also show that if G is a 2 -connected, \(\gamma _{pr}(G) = \frac{n}{3} \). Furthermore, if G is a connected \((2k+1)\)-regular \(\{K_{1,3}, K_4-e\}\)-free graph of order n, then \(\gamma _{pr}(G)\le \frac{n}{k+1} \), with equality if and only if \(G=L(F)\), where \(F\cong K_{1, 2k+2}\), or k is even and \(F\cong K_{k+1,k+2}\).     

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.     

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.     

On the <Emphasis Type="Italic">L</Emphasis>(2, 1)-labeling conjecture for brick product graphs

Let \(G=(V, E)\) be a graph. Denote \(d_G(u, v)\) the distance between two vertices u and v in G. An L(2, 1)-labeling of G is a function \(f: V \rightarrow \{0,1,\ldots \}\) such that for any two vertices u and v, \(|f(u)-f(v)| \ge 2\) if \(d_G(u, v) = 1\) and \(|f(u)-f(v)| \ge 1\) if \(d_G(u, v) = 2\). The span of f is the difference between the largest and the smallest number in f(V). The \(\lambda \)-number \(\lambda (G)\) of G is the minimum span over all L(2, 1)-labelings of G. In this paper, we conclude that the \(\lambda \)-number of each brick product graph is 5 or 6, which confirms Conjecture 6.1 stated in Li et al. (J Comb Optim 25:716–736, 2013).     

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.     

Efficient reassembling of graphs,part 1: the linear case

The reassembling of a simple connected graph \(G = (V,E)\) is an abstraction of a problem arising in earlier studies of network analysis. Its simplest formulation is in two steps:

1. (1)
   We cut every edge of G into two halves, thus obtaining a collection of \(n = |\,V\,|\) one-vertex components, such that for every \(v\in V\) the one-vertex component \(\{ v \}\) has \({{degree}}_{}(v)\) half edges attached to it.
    
2. (2)
   We splice the two halves of every edge together, not of all the edges at once, but in some ordering \(\Theta \) of the edges that minimizes two measures that depend on the edge-boundary degrees of assembled components.
    

A component A is a subset of V and its edge-boundary degree is the number of edges in G with one endpoint in A and one endpoint in \(V-A\) (which is the same as the number of half edges attached to A after all edges with both endpoints in A have been spliced together). The maximum edge-boundary degree encountered during the reassembling process is what we call the \(\varvec{\alpha }\) -measure of the reassembling, and the sum of all edge-boundary degrees is its \(\varvec{\beta }\) -measure. The \(\alpha \)-optimization (resp. \(\beta \)-optimization) of the reassembling of G is to determine an order \(\Theta \) for splicing the edges that minimizes its \(\alpha \)-measure (resp. \(\beta \)-measure). There are different forms of reassembling, depending on restrictions and variations on the ordering \(\Theta \) of the edges. We consider only cases satisfying the condition that if an edge between disjoint components A and B is spliced, then all the edges between A and B are spliced at the same time. In this report, we examine the particular case of linear reassembling, which requires that the next edge to be spliced must be adjacent to an already spliced edge. We delay other forms of reassembling to follow-up reports. We prove that \(\alpha \)-optimization of linear reassembling and minimum-cutwidth linear arrangment (\(\mathrm{CutWidth}\)) are polynomially reducible to each other, and that \(\beta \)-optimization of linear reassembling and minimum-cost linear arrangement (\(\mathrm{MinArr}\)) are polynomially reducible to each other. The known NP-hardness of \(\mathrm{CutWidth}\) and \(\mathrm{MinArr}\) imply the NP-hardness of \(\alpha \)-optimization and \(\beta \)-optimization.

     

Lambda number for the direct product of some family of graphs

An L(2, 1)-labeling for a graph \(G=(V,E)\) is a function f on V such that \(|f(u)-f(v)|\ge 2\) if u and v are adjacent and f(u) and f(v) are distinct if u and v are vertices of distance two. The L(2, 1)-labeling number, or the lambda number \(\lambda (G)\), for G is the minimum span over all L(2, 1)-labelings of G. When \(P_{m}\times C_{n}\) is the direct product of a path \(P_m\) and a cycle \(C_n\), Jha et al. (Discret Appl Math 145:317–325, 2005) computed the lambda number of \(P_{m}\times C_{n}\) for \(n\ge 3\) and \(m=4,5\). They also showed that when \(m\ge 6\) and \(n\ge 7\), \(\lambda (P_{m}\times C_{n})=6\) if and only if n is the multiple of 7 and conjectured that it is 7 if otherwise. They also showed that \(\lambda (C_{7i}\times C_{7j})=6\) for some i, j. In this paper, we show that when \(m\ge 6\) and \(n\ge 3\), \(\lambda (P_m\times C_n)=7\) if and only if n is not a multiple of 7. Consequently the conjecture is proved. Here we also provide the conditions on m and n such that \(\lambda (C_m\times C_n)\le 7\).     

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\).     

Minimum 2-distance coloring of planar graphs and channel assignment

A 2-distance k-coloring of a graph G is a proper k-coloring such that any two vertices at distance two get different colors. \(\chi _{2}(G)\)=min{k|G has a 2-distance k-coloring}. Wegner conjectured that for each planar graph G with maximum degree \(\Delta \), \(\chi _2(G) \le 7\) if \(\Delta \le 3\), \(\chi _2(G) \le \Delta +5\) if \(4\le \Delta \le 7\) and \(\chi _2(G) \le \lfloor \frac{3\Delta }{2}\rfloor +1\) if \(\Delta \ge 8\). In this paper, we prove that: (1) If G is a planar graph with maximum degree \(\Delta \le 5\), then \(\chi _{2}(G)\le 20\); (2) If G is a planar graph with maximum degree \(\Delta \ge 6\), then \(\chi _{2}(G)\le 5\Delta -7\).     

Almost separable matrices

An \(m\times n\) matrix \(\mathsf {A}\) with column supports \(\{S_i\}\) is k-separable if the disjunctions \(\bigcup _{i \in \mathcal {K}} S_i\) are all distinct over all sets \(\mathcal {K}\) of cardinality k. While a simple counting bound shows that \(m > k \log _2 n/k\) rows are required for a separable matrix to exist, in fact it is necessary for m to be about a factor of k more than this. In this paper, we consider a weaker definition of ‘almost k-separability’, which requires that the disjunctions are ‘mostly distinct’. We show using a random construction that these matrices exist with \(m = O(k \log n)\) rows, which is optimal for \(k = O(n^{1-\beta })\). Further, by calculating explicit constants, we show how almost separable matrices give new bounds on the rate of nonadaptive group testing.     

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.     

On zero-sum $$\mathbb {Z}_{2j}^k$$-magic graphs

Let \(G = (V,E)\) be a finite graph and let \((\mathbb {A},+)\) be an abelian group with identity 0. Then G is \(\mathbb {A}\)-magic if and only if there exists a function \(\phi \) from E into \(\mathbb {A} - \{0\}\) such that for some \(c \in \mathbb {A}, \sum _{e \in E(v)} \phi (e) = c\) for every \(v \in V\), where E(v) is the set of edges incident to v. Additionally, G is zero-sum \(\mathbb {A}\)-magic if and only if \(\phi \) exists such that \(c = 0\). We consider zero-sum \(\mathbb {A}\)-magic labelings of graphs, with particular attention given to \(\mathbb {A} = \mathbb {Z}_{2j}^k\). For \(j \ge 1\), let \(\zeta _{2j}(G)\) be the smallest positive integer c such that G is zero-sum \(\mathbb {Z}_{2j}^c\)-magic if c exists; infinity otherwise. We establish upper bounds on \(\zeta _{2j}(G)\) when \(\zeta _{2j}(G)\) is finite, and show that \(\zeta _{2j}(G)\) is finite for all r-regular \(G, r \ge 2\). Appealing to classical results on the factors of cubic graphs, we prove that \(\zeta _4(G) \le 2\) for a cubic graph G, with equality if and only if G has no 1-factor. We discuss the problem of classifying cubic graphs according to the collection of finite abelian groups for which they are zero-sum group-magic.     

A new sufficient condition for a tree T to have the (2, 1)-total number $$\Delta +1$$

A k-(2, 1)-total labelling of a graph G is a mapping \(f: V(G)\cup E(G)\rightarrow \{0,1,\ldots ,k\}\) such that adjacent vertices or adjacent edges receive distinct labels, and a vertex and its incident edges receive labels that differ in absolute value by at least 2. The (2, 1)-total number, denoted \(\lambda _2^t(G)\), is the minimum k such that G has a k-(2, 1)-total labelling. Let T be a tree with maximum degree \(\Delta \ge 7\). A vertex \(v\in V(T)\) is called major if \(d(v)=\Delta \), minor if \(d(v)<\Delta \), and saturated if v is major and is adjacent to exactly \(\Delta - 2\) major vertices. It is known that \(\Delta + 1 \le \lambda _2^t(T)\le \Delta + 2\). In this paper, we prove that if every major vertex is adjacent to at most \(\Delta -2\) major vertices, and every minor vertex is adjacent to at most three saturated vertices, then \(\lambda _2^t(T) = \Delta + 1\). The result is best possible with respect to these required conditions.     

List 2-distance $$\varDelta +3$$-coloring of planar graphs without 4,5-cycles

Let \(\chi _2(G)\) and \(\chi _2^l(G)\) be the 2-distance chromatic number and list 2-distance chromatic number of a graph G, respectively. Wegner conjectured that for each planar graph G with maximum degree \(\varDelta \) at least 4, \(\chi _2(G)\le \varDelta +5\) if \(4\le \varDelta \le 7\), and \(\chi _2(G)\le \lfloor \frac{3\varDelta }{2}\rfloor +1\) if \(\varDelta \ge 8\). Let G be a planar graph without 4,5-cycles. We show that if \(\varDelta \ge 26\), then \(\chi _2^l(G)\le \varDelta +3\). There exist planar graphs G with girth \(g(G)=6\) such that \(\chi _2^l(G)=\varDelta +2\) for arbitrarily large \(\varDelta \). In addition, we also discuss the list L(2, 1)-labeling number of G, and prove that \(\lambda _l(G)\le \varDelta +8\) for \(\varDelta \ge 27\).     

Pac king spanning trees and spanning 2-connected k-edge-connected essentially $$(2 k-1)$$(2 k-1)-edge-connected subgraphs

Let \(k\ge 2, p\ge 1, q\ge 0\) be integers. We prove that every \((4kp-2p+2q)\)-connected graph contains p spanning subgraphs \(G_i\) for \(1\le i\le p\) and q spanning trees such that all \(p+q\) subgraphs are pairwise edge-disjoint and such that each \(G_i\) is k-edge-connected, essentially \((2k-1)\)-edge-connected, and \(G_i -v\) is \((k-1)\)-edge-connected for all \(v\in V(G)\). This extends the well-known result of Nash-Williams and Tutte on packing spanning trees, a theorem that every 6p-connected graph contains p pairwise edge-disjoint spanning 2-connected subgraphs, and a theorem that every \((6p+2q)\)-connected graph contains p spanning 2-connected subgraphs and q spanning trees, which are all pairwise edge-disjoint. As an application, we improve a result on k-arc-connected orientations.     

Is there any polynomial upper bound for the universal labeling of graphs?

A universal labeling of a graph G is a labeling of the edge set in G such that in every orientation \(\ell \) of G for every two adjacent vertices v and u, the sum of incoming edges of v and u in the oriented graph are different from each other. The universal labeling number of a graph G is the minimum number k such that G has universal labeling from \(\{1,2,\ldots , k\}\) denoted it by \(\overrightarrow{\chi _{u}}(G) \). We have \(2\Delta (G)-2 \le \overrightarrow{\chi _{u}} (G)\le 2^{\Delta (G)}\), where \(\Delta (G)\) denotes the maximum degree of G. In this work, we offer a provocative question that is: “Is there any polynomial function f such that for every graph G, \(\overrightarrow{\chi _{u}} (G)\le f(\Delta (G))\)?”. Towards this question, we introduce some lower and upper bounds on their parameter of interest. Also, we prove that for every tree T, \(\overrightarrow{\chi _{u}}(T)={\mathcal {O}}(\Delta ^3) \). Next, we show that for a given 3-regular graph G, the universal labeling number of G is 4 if and only if G belongs to Class 1. Therefore, for a given 3-regular graph G, it is an \( {{\mathbf {N}}}{{\mathbf {P}}} \)-complete to determine whether the universal labeling number of G is 4. Finally, using probabilistic methods, we almost confirm a weaker version of the problem.     

Cost sharing on prices for games on graphs

Let \(N=\{1,\dots ,n\}\) be a set of customers who want to buy a single homogenous goods in market. Let \(q_i>0\) be the quantity that \(i\in N\) demands, \(q=(q_1,\dots ,q_n)\) and \(q_S=\sum _{i\in S}q_i\) for \(S\subseteq N\). If f(s) is a (increasing and concave) cost function, then it yields a cooperative game (N, f, q) by defining characteristic function \(v(S)=f(q_S)\) for \(S\subseteq N\). We now consider the way of taking packages of goods by customers and define a communication graph L on N, in which i and j are linked if they can take packages for each other. So if i and j are connected, then a package can be delivered from i to j by some intermediators. We thus admit any connected subset as a feasible coalition, and obtain a game (N, f, q, L) by defining characteristic function \(v_L(S)=\sum _{R\in S/L}f(q_R)\) for \(S\subseteq N\), where S / L is the family of induced components (maximal connected subset) in S. It is shown that there is an allocation (cost shares) \(x=(x_1,\dots ,x_n)\) from the core for the game (\(x_S\le v_L(S)\) for any \(S\subseteq N\)) such that x satisfies Component Efficiency and Ranking for Unit Prices. If f(s) and q satisfy some further condition, then there is an allocation x from the core such that x satisfies Component Efficiency, and \(x_i \le x_j\) and \(\frac{x_i}{q_i} \ge \frac{x_j}{q_j}\) if \(q_i \le q_j\) for i and j in the same component of N.     

Algorithms for connected <Emphasis Type="Italic">p</Emphasis>-centdian problem on block graphs

We consider the facility location problem of locating a set \(X_p\) of p facilities (resources) on a network (or a graph) such that the subnetwork (or subgraph) induced by the selected set \(X_p\) is connected. Two problems on a block graph G are proposed: one problem is to minimizes the sum of its weighted distances from all vertices of G to \(X_p\), another problem is to minimize the maximum distance from each vertex that is not in \(X_p\) to \(X_p\) and, at the same time, to minimize the sum of its distances from all vertices of G to \(X_p\). We prove that the first problem is linearly solvable on block graphs with unit edge length. For the second problem, it is shown that the set of Pareto-optimal solutions of the two criteria has cardinality not greater than n, and can be obtained in \(O(n^2)\) time, where n is the number of vertices of the block graph G.     

A quadratic time exact algorithm for continuous connected 2-facility location problem in trees

This paper studies the continuous connected 2-facility location problem (CC2FLP) in trees. Let \(T = (V, E, c, d, \ell , \mu )\) be an undirected rooted tree, where each node \(v \in V\) has a weight \(d(v) \ge 0\) denoting the demand amount of v as well as a weight \(\ell (v) \ge 0\) denoting the cost of opening a facility at v, and each edge \(e \in E\) has a weight \(c(e) \ge 0\) denoting the cost on e and is associated with a function \(\mu (e,t) \ge 0\) denoting the cost of opening a facility at a point x(e, t) on e where t is a continuous variable on e. Given a subset \(\mathcal {D} \subseteq V\) of clients, and a subset \(\mathcal {F} \subseteq \mathcal {P}(T)\) of continuum points admitting facilities where \(\mathcal {P}(T)\) is the set of all the points on edges of T, when two facilities are installed at a pair of continuum points \(x_1\) and \(x_2\) in \(\mathcal {F}\), the total cost involved in CC2FLP includes three parts: the cost of opening two facilities at \(x_1\) and \(x_2\), K times the cost of connecting \(x_1\) and \(x_2\), and the cost of all the clients in \(\mathcal {D}\) connecting to some facility. The objective is to open two facilities at a pair of continuum points in \(\mathcal {F}\) to minimize the total cost, for a given input parameter \(K \ge 1\). This paper focuses on the case of \(\mathcal {D} = V\) and \(\mathcal {F} = \mathcal {P}(T)\). We first study the discrete version of CC2FLP, named the discrete connected 2-facility location problem (DC2FLP), where two facilities are restricted to the nodes of T, and devise a quadratic time edge-splitting algorithm for DC2FLP. Furthermore, we prove that CC2FLP is almost equivalent to DC2FLP in trees, and develop a quadratic time exact algorithm based on the edge-splitting algorithm. Finally, we adapt our algorithms to the general case of \(\mathcal {D} \subseteq V\) and \(\mathcal {F} \subseteq \mathcal {P}(T)\).