On minimally 2-connected graphs with generalized connectivity $$\kappa _{3}=2$$

For \(S\subseteq G\), let \(\kappa (S)\) denote the maximum number r of edge-disjoint trees \(T_1, T_2, \ldots , T_r\) in G such that \(V(T_i)\cap V(T_j)=S\) for any \(i,j\in \{1,2,\ldots ,r\}\) and \(i\ne j\). For every \(2\le k\le n\), the k-connectivity of G, denoted by \(\kappa _k(G)\), is defined as \(\kappa _k(G)=\hbox {min}\{\kappa (S)| S\subseteq V(G)\ and\ |S|=k\}\). Clearly, \(\kappa _2(G)\) corresponds to the traditional connectivity of G. In this paper, we focus on the structure of minimally 2-connected graphs with \(\kappa _{3}=2\). Denote by \(\mathcal {H}\) the set of minimally 2-connected graphs with \(\kappa _{3}=2\). Let \(\mathcal {B}\subseteq \mathcal {H}\) and every graph in \(\mathcal {B}\) is either \(K_{2,3}\) or the graph obtained by subdividing each edge of a triangle-free 3-connected graph. We obtain that \(H\in \mathcal {H}\) if and only if \(H\in \mathcal {B}\) or H can be constructed from one or some graphs \(H_{1},\ldots ,H_{k}\) in \(\mathcal {B}\) (\(k\ge 1\)) by applying some operations recursively.     

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.     

2-Edge connected dominating sets and 2-Connected dominating sets of a graph

A \(k\)-connected (resp. \(k\)-edge connected) dominating set \(D\) of a connected graph \(G\) is a subset of \(V(G)\) such that \(G[D]\) is \(k\)-connected (resp. \(k\)-edge connected) and each \(v\in V(G)\backslash D\) has at least one neighbor in \(D\). The \(k\) -connected domination number (resp. \(k\) -edge connected domination number) of a graph \(G\) is the minimum size of a \(k\)-connected (resp. \(k\)-edge connected) dominating set of \(G\), and denoted by \(\gamma _k(G)\) (resp. \(\gamma '_k(G)\)). In this paper, we investigate the relation of independence number and 2-connected (resp. 2-edge-connected) domination number, and prove that for a graph \(G\), if it is \(2\)-edge connected, then \(\gamma '_2(G)\le 4\alpha (G)-1\), and it is \(2\)-connected, then \(\gamma _2(G)\le 6\alpha (G)-3\), where \(\alpha (G)\) is the independent number of \(G\).     

Improved approximations for buy-at-bul and shallow-light $$$$-Steiner trees and $$(,2)$$(,2)-subgraph

In this paper we give improved approximation algorithms for some network design problems. In the bounded-diameter or shallow-light \(k\)-Steiner tree problem (SL\(k\)ST), we are given an undirected graph \(G=(V,E)\) with terminals \(T\subseteq V\) containing a root \(r\in T\), a cost function \(c:E\rightarrow \mathbb {R}^+\), a length function \(\ell :E\rightarrow \mathbb {R}^+\), a bound \(L>0\) and an integer \(k\ge 1\). The goal is to find a minimum \(c\)-cost \(r\)-rooted Steiner tree containing at least \(k\) terminals whose diameter under \(\ell \) metric is at most \(L\). The input to the buy-at-bulk \(k\)-Steiner tree problem (BB\(k\)ST) is similar: graph \(G=(V,E)\), terminals \(T\subseteq V\) containing a root \(r\in T\), cost and length functions \(c,\ell :E\rightarrow \mathbb {R}^+\), and an integer \(k\ge 1\). The goal is to find a minimum total cost \(r\)-rooted Steiner tree \(H\) containing at least \(k\) terminals, where the cost of each edge \(e\) is \(c(e)+\ell (e)\cdot f(e)\) where \(f(e)\) denotes the number of terminals whose path to root in \(H\) contains edge \(e\). We present a bicriteria \((O(\log ^2 n),O(\log n))\)-approximation for SL\(k\)ST: the algorithm finds a \(k\)-Steiner tree with cost at most \(O(\log ^2 n\cdot \text{ opt }^*)\) where \(\text{ opt }^*\) is the cost of an LP relaxation of the problem and diameter at most \(O(L\cdot \log n)\). This improves on the algorithm of Hajiaghayi et al. (2009) (APPROX’06/Algorithmica’09) which had ratio \((O(\log ^4 n), O(\log ^2 n))\). Using this, we obtain an \(O(\log ^3 n)\)-approximation for BB\(k\)ST, which improves upon the \(O(\log ^4 n)\)-approximation of Hajiaghayi et al. (2009). We also consider the problem of finding a minimum cost \(2\)-edge-connected subgraph with at least \(k\) vertices, which is introduced as the \((k,2)\)-subgraph problem in Lau et al. (2009) (STOC’07/SICOMP09). This generalizes some well-studied classical problems such as the \(k\)-MST and the minimum cost \(2\)-edge-connected subgraph problems. We give an \(O(\log n)\)-approximation algorithm for this problem which improves upon the \(O(\log ^2 n)\)-approximation algorithm of Lau et al. (2009).     

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.     

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.     

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

Maximum coverage problem with group budget constraints

We study the maximum coverage problem with group budget constraints (MCG). The input consists of a ground set X, a collection \(\psi \) of subsets of X each of which is associated with a combinatorial structure such that for every set \(S_j\in \psi \), a cost \(c(S_j)\) can be calculated based on the combinatorial structure associated with \(S_j\), a partition \(G_1,G_2,\ldots ,G_l\) of \(\psi \), and budgets \(B_1,B_2,\ldots ,B_l\), and B. A solution to the problem consists of a subset H of \(\psi \) such that \(\sum _{S_j\in H} c(S_j) \le B\) and for each \(i \in {1,2,\ldots ,l}\), \(\sum _{S_j \in H\cap G_i}c(S_j)\le B_i\). The objective is to maximize \(|\bigcup _{S_j\in H}S_j|\). In our work we use a new and improved analysis of the greedy algorithm to prove that it is a \((\frac{\alpha }{3+2\alpha })\)-approximation algorithm, where \(\alpha \) is the approximation ratio of a given oracle which takes as an input a subset \(X^{new}\subseteq X\) and a group \(G_i\) and returns a set \(S_j\in G_i\) which approximates the optimal solution for \(\max _{D\in G_i}\frac{|D\cap X^{new}|}{c(D)}\). This analysis that is shown here to be tight for the greedy algorithm, improves by a factor larger than 2 the analysis of the best known approximation algorithm for MCG.     

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

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.     

A $$(3,1)^{*}$$-choosable theorem on planar graphs

A list assignment of a graph G is a function L that assigns a list L(v) of colors to each vertex \(v\in V(G)\). An \((L,d)^*\)-coloring is a mapping \(\pi \) that assigns a color \(\pi (v)\in L(v)\) to each vertex \(v\in V(G)\) so that at most d neighbors of v receive color \(\pi (v)\). A graph G is said to be \((k,d)^*\)-choosable if it admits an \((L,d)^*\)-coloring for every list assignment L with \(|L(v)|\ge k\) for all \(v\in V(G)\). In this paper, we prove that every planar graph with neither adjacent triangles nor 6-cycles is \((3,1)^*\)-choosable. This is a partial answer to a question of Xu and Zhang (Discret Appl Math 155:74–78, 2007) that every planar graph without adjacent triangles is \((3,1)^*\)-choosable. Also, this improves a result in Lih et al. (Appl Math Lett 14:269–273, 2001) which says that every planar graph without 4- and 6-cycles is \((3,1)^*\)-choosable.     

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.     

A simple approximation algorithm for minimum weight partial connected set cover

Let \(LTQ_n\) be the n-dimensional locally twisted cube. Hsieh and Tu (Theor Comput Sci 410(8–10):926–932, 2009) proposed an algorithm to construct n edge-disjoint spanning trees rooted at a particular vertex 0 in \(LTQ_n\). Later on, Lin et al. (Inf Process Lett 110(10):414–419, 2010) proved that Hsieh and Tu’s spanning trees are indeed independent spanning trees (ISTs for short), i.e., all spanning trees are rooted at the same vertex r and for any other vertex \(v(\ne r)\), the paths from v to r in any two trees are internally vertex-disjoint. Shortly afterwards, Liu et al. (Theor Comput Sci 412(22):2237–2252, 2011) pointed out that \(LTQ_n\) fails to be vertex-transitive for \(n\geqslant 4\) and proposed an algorithm for constructing n ISTs rooted at an arbitrary vertex in \(LTQ_n\). Although this algorithm can simultaneously construct n ISTs, it is hard to be parallelized for the construction of each spanning tree. In this paper, from a modification of Hsieh and Tu’s algorithm, we present a fully parallelized scheme to construct n ISTs rooted at an arbitrary vertex in \(LTQ_n\) in \({\mathcal O}(n)\) time using \(2^n\) vertices of \(LTQ_n\) as processors.     

L(2,1)-labelings of the edge-multiplicity-paths-replacement of a graph

An L(2,1)-labeling of a graph \(G\) is an assignment of nonnegative integers to \(V(G)\) such that the difference between labels of adjacent vertices is at least \(2\), and the difference between labels of vertices that are distance two apart is at least 1. The span of an L(2,1)-labeling of a graph \(G\) is the difference between the maximum and minimum integers used by it. The minimum span of an L(2,1)-labeling of \(G\) is denoted by \(\lambda (G)\). This paper focuses on L(2,1)-labelings-number of the edge-multiplicity-paths-replacement \(G(rP_{k})\) of a graph \(G\). In this paper, we obtain that \( r\Delta +1 \le \lambda (G(rP_{5}))\le r\Delta +2\), \(\lambda (G(rP_{k}))= r\Delta +1\) for \(k\ge 6\); and \(\lambda (G(rP_{4}))\le (\Delta +1)r+1\), \(\lambda (G(rP_{3}))\le (\Delta +1)r+\Delta \) for any graph \(G\) with maximum degree \(\Delta \). And the L(2,1)-labelings-numbers of the edge-multiplicity-paths-replacement \(G(rP_{k})\) are completely determined for \(1\le \Delta \le 2\). And we show that the class of graphs \(G(rP_{k})\) with \(k\ge 3 \) satisfies the conjecture: \(\lambda ^{T}_{2}(G)\le \Delta +2\) by Havet and Yu (Technical Report 4650, 2002).     

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

Relation between the skew-rank of an oriented graph and the independence number of its underlying graph

An oriented graph \(G^\sigma \) is a digraph without loops or multiple arcs whose underlying graph is G. Let \(S\left( G^\sigma \right) \) be the skew-adjacency matrix of \(G^\sigma \) and \(\alpha (G)\) be the independence number of G. The rank of \(S(G^\sigma )\) is called the skew-rank of \(G^\sigma \), denoted by \(sr(G^\sigma )\). Wong et al. (Eur J Comb 54:76–86, 2016) studied the relationship between the skew-rank of an oriented graph and the rank of its underlying graph. In this paper, the correlation involving the skew-rank, the independence number, and some other parameters are considered. First we show that \(sr(G^\sigma )+2\alpha (G)\geqslant 2|V_G|-2d(G)\), where \(|V_G|\) is the order of G and d(G) is the dimension of cycle space of G. We also obtain sharp lower bounds for \(sr(G^\sigma )+\alpha (G),\, sr(G^\sigma )-\alpha (G)\), \(sr(G^\sigma )/\alpha (G)\) and characterize all corresponding extremal graphs.     

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

An FPTAS for generalized absolute 1-center problem in vertex-weighted graphs

Given a vertex-weighted undirected connected graph \(G = (V, E, \ell , \rho )\), where each edge \(e \in E\) has a length \(\ell (e) > 0\) and each vertex \(v \in V\) has a weight \(\rho (v) > 0\), a subset \(T \subseteq V\) of vertices and a set S containing all the points on edges in a subset \(E' \subseteq E\) of edges, the generalized absolute 1-center problem (GA1CP), an extension of the classic vertex-weighted absolute 1-center problem (A1CP), asks to find a point from S such that the longest weighted shortest path distance in G from it to T is minimized. This paper presents a simple FPTAS for GA1CP by traversing the edges in \(E'\) using a positive real number as step size. The FPTAS takes \(O( |E| |V| + |V|^2 \log \log |V| + \frac{1}{\epsilon } |E'| |T| {\mathcal {R}})\) time, where \({\mathcal {R}}\) is an input parameter size of the problem instance, for any given \(\epsilon > 0\). For instances with a small input parameter size \({\mathcal {R}}\), applying the FPTAS with \(\epsilon = \Theta (1)\) to the classic vertex-weighted A1CP can produce a \((1 + \Theta (1))\)-approximation in at most O(|E| |V|) time when the distance matrix is known and \(O(|E| |V| + |V|^2 \log \log |V|)\) time when the distance matrix is unknown, which are smaller than Kariv and Hakimi’s \(O(|E| |V| \log |V|)\)-time algorithm and \(O(|E| |V| \log |V| + |V|^3)\)-time algorithm, respectively.     

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.     

Bounds on the domination number of a digraph

A vertex subset S of a digraph D is called a dominating set of D if every vertex not in S is adjacent from at least one vertex in S. The domination number of D, denoted by \(\gamma (D)\), is the minimum cardinality of a dominating set of D. The Slater number \(s\ell (D)\) is the smallest integer t such that t added to the sum of the first t terms of the non-increasing out-degree sequence of D is at least as large as the order of D. For any digraph D of order n with maximum out-degree \(\Delta ^+\), it is known that \(\gamma (D)\ge \lceil n/(\Delta ^++1)\rceil \). We show that \(\gamma (D)\ge s\ell (D)\ge \lceil n/(\Delta ^++1)\rceil \) and the difference between \(s\ell (D)\) and \(\lceil n/(\Delta ^++1)\rceil \) can be arbitrarily large. In particular, for an oriented tree T of order n with \(n_0\) vertices of out-degree 0, we show that \((n-n_0+1)/2\le s\ell (T)\le \gamma (T)\le 2s\ell (T)-1\) and moreover, each value between the lower bound \(s\ell (T)\) and the upper bound \(2s\ell (T)-1\) is attainable by \(\gamma (T)\) for some oriented trees. Further, we characterize the oriented trees T for which \(s\ell (T)=(n-n_0+1)/2\) hold and show that the difference between \(s\ell (T)\) and \((n-n_0+1)/2\) can be arbitrarily large. Some other elementary properties involving the Slater number are also presented.