Bandwidth sums of block graphs and cacti

A labeling of a graph G is an injective function f:V(G)→?. The bandwidth sum of a graph G with respect to a labeling f is $B_{s}^{f}(G) = \sum_{uv \in E(G)} |f(u)-f(v)|$ and the bandwidth sum of G is $B_{s}(G) = \min\{B_{s}^{f}(G)\colon f\mbox{ is a labeling of }G\}$ . In this paper, we determine bandwidth sums for some block graphs and cacti.     

L(d,1)-labelings of the edge-path-replacement of a graph

For two positive integers j and k with j≥k, an L(j,k)-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 j, and the difference between labels of vertices that are distance two apart is at least k. The span of an L(j,k)-labeling of a graph G is the difference between the maximum and minimum integers used by it. The L(j,k)-labelings-number of G is the minimum span over all L(j,k)-labelings of G. This paper focuses on L(d,1)-labelings-number of the edge-path-replacement G(P _k ) of a graph G. Note that G(P ₃) is the incidence graph of G. L(d,1)-labelings of the edge-path-replacement G(P _k ) of a graph, called (d,1)-total labeling of G, was introduced in 2002 by Havet and Yu (Workshop graphs and algorithms, 2003; Discrete Math 308:493–513, 2008). Havet and Yu (Discrete Math 308:498–513, 2008) obtained the bound $\Delta+ d-1\leq\lambda^{T}_{d}(G)\leq2\Delta+ d-1$ and conjectured $\lambda^{T}_{d}(G)\leq\Delta+2d-1$ . In (Lü in J Comb Optim, to appear; Zhejiang University, submitted), we worked on L(2,1)-labelings-number and L(1,1)-labelings-number of the edge-path-replacement G(P _k ) of a graph G, and obtained that λ(G(P _k ))≤Δ+2 for k≥5, and conjecture λ(G(P ₄))≤Δ+2 for any graph G with maximum degree Δ. In this paper, we will study L(d,1)-labelings-number of the edge-path-replacement G(P _k ) of a graph G for d≥3 and k≥4.     

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

For two positive integers j and k with j≥k, an L(j,k)-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 j, and the difference between labels of vertices that are distance two apart is at least k. The span of an L(j,k)-labeling of a graph G is the difference between the maximum and minimum integers used by it. The L(j,k)-labelings-number of G is the minimum span over all L(j,k)-labelings of G. This paper focuses on L(2,1)-labelings-number of the edge-path-replacement G(P _k ) of a graph G. Note that G(P ₃) is the incidence graph of G. L(2,1)-labelings of the edge-path-replacement G(P ₃) of a graph, called (2,1)-total labeling of G, was introduced by Havet and Yu in 2002 (Workshop graphs and algorithms, Dijon, France, 2003; Discrete Math. 308:498–513, 2008). They (Havet and Yu, Discrete Math. 308:498–513, 2008) obtain the bound $\Delta+1\leq\lambda^{T}_{2}(G)\leq2\Delta+1$ and conjectured $\lambda^{T}_{2}(G)\leq\Delta+3$ . In this paper, we obtain that λ(G(P _k ))≤Δ+2 for k≥5, and conjecture λ(G(P ₄))≤Δ+2 for any graph G with maximum degree Δ.     

Signed Roman domination in graphs

In this paper we continue the study of Roman dominating functions in graphs. A signed Roman dominating function (SRDF) on a graph G=(V,E) is a function f:V→{?1,1,2} satisfying the conditions that (i) the sum of its function values over any closed neighborhood is at least one and (ii) for every vertex u for which f(u)=?1 is adjacent to at least one vertex v for which f(v)=2. The weight of a SRDF is the sum of its function values over all vertices. The signed Roman domination number of G is the minimum weight of a SRDF in G. We present various lower and upper bounds on the signed Roman domination number of a graph. Let G be a graph of order n and size m with no isolated vertex. We show that $\gamma _{\mathrm{sR}}(G) \ge\frac{3}{\sqrt{2}} \sqrt{n} - n$ and that γ _sR(G)≥(3n?4m)/2. In both cases, we characterize the graphs achieving equality in these bounds. If G is a bipartite graph of order n, then we show that $\gamma_{\mathrm{sR}}(G) \ge3\sqrt{n+1} - n - 3$ , and we characterize the extremal graphs.     

Hardness results and approximation algorithm for total liar’s domination in graphs

In this paper, we initiate the study of total liar’s domination of a graph. A subset L?V of a graph G=(V,E) is called a total liar’s dominating set of G if (i) for all v∈V, |N _G (v)∩L|≥2 and (ii) for every pair u,v∈V of distinct vertices, |(N _G (u)∪N _G (v))∩L|≥3. The total liar’s domination number of a graph G is the cardinality of a minimum total liar’s dominating set of G and is denoted by γ _TLR (G). The Minimum Total Liar’s Domination Problem is to find a total liar’s dominating set of minimum cardinality of the input graph G. Given a graph G and a positive integer k, the Total Liar’s Domination Decision Problem is to check whether G has a total liar’s dominating set of cardinality at most k. In this paper, we give a necessary and sufficient condition for the existence of a total liar’s dominating set in a graph. We show that the Total Liar’s Domination Decision Problem is NP-complete for general graphs and is NP-complete even for split graphs and hence for chordal graphs. We also propose a 2(lnΔ(G)+1)-approximation algorithm for the Minimum Total Liar’s Domination Problem, where Δ(G) is the maximum degree of the input graph G. We show that Minimum Total Liar’s Domination Problem cannot be approximated within a factor of $(\frac{1}{8}-\epsilon)\ln(|V|)$ for any ?>0, unless NP?DTIME(|V|^loglog|V|). Finally, we show that Minimum Total Liar’s Domination Problem is APX-complete for graphs with bounded degree 4.     

The total domination subdivision number in graphs with no induced 3-cycle and 5-cycle

A set S of vertices of a graph G=(V,E) without isolated vertex is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination number γ _t (G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number $\mathrm{sd}_{\gamma_{t}}(G)$ is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the total domination number. Favaron, Karami, Khoeilar and Sheikholeslami (J. Comb. Optim. 20:76–84, 2010a) conjectured that: For any connected graph G of order n≥3, $\mathrm{sd}_{\gamma_{t}}(G)\le \gamma_{t}(G)+1$ . In this paper we use matching to prove this conjecture for graphs with no 3-cycle and 5-cycle. In particular this proves the conjecture for bipartite graphs.     

FPT algorithms for Connected Feedback Vertex Set

We study the recently introduced Connected Feedback Vertex Set (CFVS) problem from the view-point of parameterized algorithms. CFVS is the connected variant of the classical Feedback Vertex Set problem and is defined as follows: given a graph G=(V,E) and an integer k, decide whether there exists F?V, |F|??k, such that G[V?F] is a forest and G[F] is connected. We show that Connected Feedback Vertex Set can be solved in time O(2 ^O(k) n ^O(1)) on general graphs and in time $O(2^{O(\sqrt{k}\log k)}n^{O(1)})$ on graphs excluding a fixed graph H as a minor. Our result on general undirected graphs uses, as a subroutine, a parameterized algorithm for Group Steiner Tree, a well studied variant of Steiner Tree. We find the algorithm for Group Steiner Tree of independent interest and believe that it could be useful for obtaining parameterized algorithms for other connectivity problems.     

The total {k}-domatic number of a graph

For a positive integer k, a total {k}-dominating function of a graph G is a function f from the vertex set V(G) to the set {0,1,2,…,k} such that for any vertex v∈V(G), the condition ∑ _u∈N(v) f(u)≥k is fulfilled, where N(v) is the open neighborhood of v. A set {f ₁,f ₂,…,f _d } of total {k}-dominating functions on G with the property that ?_i=1^df_i(v) ￡ k\sum_{i=1}^{d}f_{i}(v)\le k for each v∈V(G), is called a total {k}-dominating family (of functions) on G. The maximum number of functions in a total {k}-dominating family on G is the total {k}-domatic number of G, denoted by d_t^{k}(G)d_{t}^{\{k\}}(G). Note that d_t^{1}(G)d_{t}^{\{1\}}(G) is the classic total domatic number d _t (G). In this paper we initiate the study of the total {k}-domatic number in graphs and we present some bounds for d_t^{k}(G)d_{t}^{\{k\}}(G). Many of the known bounds of d _t (G) are immediate consequences of our results.     

Distance domination in graphs with given minimum and maximum degree

For an integer \(k \ge 1\), a distance k-dominating set of a connected graph G is a set S of vertices of G such that every vertex of V(G) is at distance at most k from some vertex of S. The distance k-domination number \(\gamma _k(G)\) of G is the minimum cardinality of a distance k-dominating set of G. In this paper, we establish an upper bound on the distance k-domination number of a graph in terms of its order, minimum degree and maximum degree. We prove that for \(k \ge 2\), if G is a connected graph with minimum degree \(\delta \ge 2\) and maximum degree \(\Delta \) and of order \(n \ge \Delta + k - 1\), then \(\gamma _k(G) \le \frac{n + \delta - \Delta }{\delta + k - 1}\). This result improves existing known results.     

On the outer-connected domination in graphs

A set S of vertices of a graph G is an outer-connected dominating set if every vertex not in S is adjacent to some vertex in S and the subgraph induced by V?S is connected. The outer-connected domination number $\widetilde{\gamma}_{c}(G)$ is the minimum size of such a set. We prove that if δ(G)≥2 and diam?(G)≤2, then $\widetilde{\gamma}_{c}(G)\le (n+1)/2$ , and we study the behavior of $\widetilde{\gamma}_{c}(G)$ under an edge addition.     

L(p,q)-labeling of sparse graphs

Let p and q be positive integers. An L(p,q)-labeling of a graph G with a span s is a labeling of its vertices by integers between 0 and s such that adjacent vertices of G are labeled using colors at least p apart, and vertices having a common neighbor are labeled using colors at least q apart. We denote by λ _p,q (G) the least integer k such that G has an L(p,q)-labeling with span k. The maximum average degree of a graph G, denoted by $\operatorname {Mad}(G)$ , is the maximum among the average degrees of its subgraphs (i.e. $\operatorname {Mad}(G) = \max\{\frac{2|E(H)|}{|V(H)|} ; H \subseteq G \}$ ). We consider graphs G with $\operatorname {Mad}(G) < \frac{10}{3}$ , 3 and $\frac{14}{5}$ . These sets of graphs contain planar graphs with girth 5, 6 and 7 respectively. We prove in this paper that every graph G with maximum average degree m and maximum degree Δ has:

λ _p,q (G)≤(2q?1)Δ+6p+10q?8 if $m < \frac{10}{3}$ and p≥2q.

λ _p,q (G)≤(2q?1)Δ+4p+14q?9 if $m < \frac{10}{3}$ and 2q>p.

λ _p,q (G)≤(2q?1)Δ+4p+6q?5 if m<3.

λ _p,q (G)≤(2q?1)Δ+4p+4q?4 if $m < \frac{14}{5}$ .

We give also some refined bounds for specific values of p, q, or Δ. By the way we improve results of Lih and Wang (SIAM J. Discrete Math. 17(2):264–275, 2003).     

Distance two edge labelings of lattices

Suppose G is a graph. Two edges e and e′ in G are said to be adjacent if they share a common end vertex, and distance two apart if they are nonadjacent but both are adjacent to a common edge. Let j and k be two positive integers. An L(j,k)-edge-labeling of a graph G is an assignment of nonnegative integers, called labels, to the edges of G such that the difference between labels of any two adjacent edges is at least j, and the difference between labels of any two edges that are distance two apart is at least k. The minimum range of labels over all L(j,k)-edge-labelings of a graph G is called the L(j,k)-edge-labeling number of G, denoted by $\lambda_{j,k}'(G)$ . Let m, j and k be positive integers. An m-circular-L(j,k)-edge-labeling of a graph G is an assignment f from {0,1,…,m?1} to the edges of G such that, for any two edges e and e′, |f(e)?f(e′)| _m ≥j if e and e′ are adjacent, and |f(e)?f(e′)| _m ≥k if e and e′ are distance two apart, where |a| _m =min{a,m?a}. The minimum m such that G has an m-circular-L(j,k)-edge-labeling is called the circular-L(j,k)-edge-labeling number of G, denoted by $\sigma_{j,k}'(G)$ . This paper investigates the L(1,1)-edge-labeling numbers, the L(2,1)-edge-labeling numbers and the circular-L(2,1)-edge-labeling numbers of the hexagonal lattice, the square lattice, the triangular lattice and the strong product of two infinite paths.     

Some results on the injective chromatic number of?graphs

A k-coloring of a graph G=(V,E) is a mapping c:V??{1,2,??,k}. The coloring c is injective if, for every vertex v??V, all the neighbors of v are assigned with distinct colors. The injective chromatic number ?? _i (G) of G is the smallest k such that G has an injective k-coloring. In this paper, we prove that every K ₄-minor free graph G with maximum degree ????1 has $\chi_{i}(G)\le \lceil \frac{3}{2}\Delta\rceil$ . Moreover, some related results and open problems are given.     

On irreducible no-hole <Emphasis Type="Italic">L</Emphasis>(2, 1)-coloring of subdivision of graphs

An L(2, 1)-coloring (or labeling) of a graph G is a mapping \(f:V(G) \rightarrow \mathbb {Z}^{+}\bigcup \{0\}\) such that \(|f(u)-f(v)|\ge 2\) for all edges uv of G, and \(|f(u)-f(v)|\ge 1\) if u and v are at distance two in G. The span of an L(2, 1)-coloring f, denoted by span f, is the largest integer assigned by f to some vertex of the graph. The span of a graph G, denoted by \(\lambda (G)\), is min {span \(f: f\text {is an }L(2,1)\text {-coloring of } G\}\). If f is an L(2, 1)-coloring of a graph G with span k then an integer l is a hole in f, if \(l\in (0,k)\) and there is no vertex v in G such that \(f(v)=l\). A no-hole coloring is defined to be an L(2, 1)-coloring with span k which uses all the colors from \(\{0,1,\ldots ,k\}\), for some integer k not necessarily the span of the graph. An L(2, 1)-coloring is said to be irreducible if colors of no vertices in the graph can be decreased and yield another L(2, 1)-coloring of the same graph. An irreducible no-hole coloring of a graph G, also called inh-coloring of G, is an L(2, 1)-coloring of G which is both irreducible and no-hole. The lower inh-span or simply inh-span of a graph G, denoted by \(\lambda _{inh}(G)\), is defined as \(\lambda _{inh}(G)=\min ~\{\)span f : f is an inh-coloring of G}. Given a graph G and a function h from E(G) to \(\mathbb {N}\), the h-subdivision of G, denoted by \(G_{(h)}\), is the graph obtained from G by replacing each edge uv in G with a path of length h(uv). In this paper we show that \(G_{(h)}\) is inh-colorable for \(h(e)\ge 2\), \(e\in E(G)\), except the case \(\Delta =3\) and \(h(e)=2\) for at least one edge but not for all. Moreover we find the exact value of \(\lambda _{inh}(G_{(h)})\) in several cases and give upper bounds of the same in the remaining.     

Star list chromatic number of planar subcubic graphs

A proper coloring of the vertices of a graph G is called a star-coloring if the union of every two color classes induces a star forest. The graph G is L-star-colorable if for a given list assignment L there is a star-coloring π such that π(v)∈L(v). If G is L-star-colorable for any list assignment L with |L(v)|≥k for all v∈V(G), then G is called k-star-choosable. The star list chromatic number of G, denoted by $\chi_{s}^{l}(G)$ , is the smallest integer k such that G is k-star-choosable. In this paper, we prove that every planar subcubic graph is 6-star-choosable.     

Profile minimization on compositions of graphs

The profile minimization problem arose from the study of sparse matrix technique. In terms of graphs, the problem is to determine the profile of a graph G which is defined as $$P(G)=\min\limits_{f}\sum\limits_{v\in V(G)}\max\limits_{x\in N[v]}(f(v)-f(x)),$$ where f runs over all bijections from V(G) to {1,2,…,|V(G)|} and N[v]={v}∪{x∈V(G):xv∈E(G)}. This is equivalent to the interval graph completion problem, which is to find a super-graph of a graph G with as few number of edges as possible. The purpose of this paper is to study the profiles of compositions of two graphs.     

Neighbor sum distinguishing total choosability of planar graphs

A total-k-coloring of a graph G is a mapping \(c: V(G)\cup E(G)\rightarrow \{1, 2,\dots , k\}\) such that any two adjacent or incident elements in \(V(G)\cup E(G)\) receive different colors. For a total-k-coloring of G, let \(\sum _c(v)\) denote the total sum of colors of the edges incident with v and the color of v. If for each edge \(uv\in E(G)\), \(\sum _c(u)\ne \sum _c(v)\), then we call such a total-k-coloring neighbor sum distinguishing. The least number k needed for such a coloring of G is the neighbor sum distinguishing total chromatic number, denoted by \(\chi _{\Sigma }^{''}(G)\). Pil?niak and Wo?niak conjectured \(\chi _{\Sigma }^{''}(G)\le \Delta (G)+3\) for any simple graph with maximum degree \(\Delta (G)\). In this paper, we prove that for any planar graph G with maximum degree \(\Delta (G)\), \(ch^{''}_{\Sigma }(G)\le \max \{\Delta (G)+3,16\}\), where \(ch^{''}_{\Sigma }(G)\) is the neighbor sum distinguishing total choosability of G.     

Popularity at minimum cost

We consider an extension of the popular matching problem in this paper. The input to the popular matching problem is a bipartite graph $G = (\mathcal{A}\cup\mathcal{B},E)$ , where $\mathcal{A}$ is a set of people, $\mathcal{B}$ is a set of items, and each person $a \in\mathcal{A}$ ranks a subset of items in order of preference, with ties allowed. The popular matching problem seeks to compute a matching M ^? between people and items such that there is no matching M where more people are happier with M than with M ^?. Such a matching M ^? is called a popular matching. However, there are simple instances where no popular matching exists. Here we consider the following natural extension to the above problem: associated with each item $b \in\mathcal{B}$ is a non-negative price cost(b), that is, for any item b, new copies of b can be added to the input graph by paying an amount of cost(b) per copy. When G does not admit a popular matching, the problem is to “augment” G at minimum cost such that the new graph admits a popular matching. We show that this problem is NP-hard; in fact, it is NP-hard to approximate it within a factor of $\sqrt{n_{1}}/2$ , where n ₁ is the number of people. This problem has a simple polynomial time algorithm when each person has a preference list of length at most 2. However, if we consider the problem of constructing a graph at minimum cost that admits a popular matching that matches all people, then even with preference lists of length 2, the problem becomes NP-hard. On the other hand, when the number of copies of each item is fixed, we show that the problem of computing a minimum cost popular matching or deciding that no popular matching exists can be solved in O(mn ₁) time, where m is the number of edges.     

The decycling number of outerplanar graphs

For a graph G, let τ(G) be the decycling number of G and c(G) be the number of vertex-disjoint cycles of G. It has been proved that c(G)≤τ(G)≤2c(G) for an outerplanar graph G. An outerplanar graph G is called lower-extremal if τ(G)=c(G) and upper-extremal if τ(G)=2c(G). In this paper, we provide a necessary and sufficient condition for an outerplanar graph being upper-extremal. On the other hand, we find a class $\mathcal{S}$ of outerplanar graphs none of which is lower-extremal and show that if G has no subdivision of S for all $S\in \mathcal{S}$ , then G is lower-extremal.     

Spanning 3-connected index of graphs

For an integer $s>0$ and for $u,v\in V(G)$ with $u\ne v$ , an $(s;u,v)$ -path-system of G is a subgraph H of G consisting of s internally disjoint (u, v)-paths, and such an H is called a spanning $(s;u,v)$ -path system if $V(H)=V(G)$ . The spanning connectivity $\kappa ^{*}(G)$ of graph G is the largest integer s such that for any integer k with $1\le k \le s$ and for any $u,v\in V(G)$ with $u\ne v$ , G has a spanning ( $k;u,v$ )-path-system. Let G be a simple connected graph that is not a path, a cycle or a $K_{1,3}$ . The spanning k-connected index of G, written $s_{k}(G)$ , is the smallest nonnegative integer m such that $L^m(G)$ is spanning k-connected. Let $l(G)=\max \{m:\,G$ has a divalent path of length m that is not both of length 2 and in a $K_{3}$ }, where a divalent path in G is a path whose interval vertices have degree two in G. In this paper, we prove that $s_{3}(G)\le l(G)+6$ . The key proof to this result is that every connected 3-triangular graph is 2-collapsible.