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.     

L(j,k)- and circular L(j,k)-labellings for the products of complete graphs

Let j and k be two positive integers with j≥k. An L(j,k)-labelling of a graph G is an assignment of nonnegative integers to the vertices of G such that the difference between labels of any two adjacent vertices is at least j, and the difference between labels of any two vertices that are at distance two apart is at least k. The minimum range of labels over all L(j,k)-labellings of a graph G is called the λ _j,k -number of G, denoted by λ _j,k (G). A σ(j,k)-circular labelling with span m of a graph G is a function f:V(G)→{0,1,…,m−1} such that |f(u)−f(v)| _m ≥j if u and v are adjacent; and |f(u)−f(v)| _m ≥k if u and v are at distance two apart, where |x| _m =min {|x|,m−|x|}. The minimum m such that there exists a σ(j,k)-circular labelling with span m for G is called the σ _j,k -number of G and denoted by σ _j,k (G). The λ _j,k -numbers of Cartesian products of two complete graphs were determined by Georges, Mauro and Stein ((2000) SIAM J Discret Math 14:28–35). This paper determines the λ _j,k -numbers of direct products of two complete graphs and the σ _j,k -numbers of direct products and Cartesian products of two complete graphs. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday. This work is partially supported by FRG, Hong Kong Baptist University, Hong Kong; NSFC, China, grant 10171013; and Southeast University Science Foundation grant XJ0607230.     

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.     

An $$O(|E(G)|^2)$$ algorithm for recognizing Pfaffian graphs of a type of bipartite graphs

A graph \(G=(V,E)\) with even number vertices is called Pfaffian if it has a Pfaffian orientation, namely it admits an orientation such that the number of edges of any M-alternating cycle which have the same direction as the traversal direction is odd for some perfect matching M of the graph G. In this paper, we obtain a necessary and sufficient condition of Pfaffian graphs in a type of bipartite graphs. Then, we design an \(O(|E(G)|^2)\) algorithm for recognizing Pfaffian graphs in this class and constructs a Pfaffian orientation if the graph is Pfaffian. The results improve and generalize some known results.     

The total {k}-domatic number of wheels and complete graphs

Let k be a positive integer and let G be a graph with vertex set V(G). The total {k}-dominating function (T{k}DF) of a graph G is a function f from V(G) to the set {0,1,2,??,k}, such that for each vertex v??V(G), the sum of the values of all its neighbors assigned by f is at least k. A set {f ₁,f ₂,??,f _d } of pairwise different T{k}DFs of G with the property that $\sum_{i=1}^{d}f_{i}(v)\leq k$ for each v??V(G), is called a total {k}-dominating family (T{k}D family) of G. The total {k}-domatic number of a graph G, denoted by $d_{t}^{\{k\}}(G)$ , is the maximum number of functions in a T{k}D family. In this paper, we determine the exact values of the total {k}-domatic numbers of wheels and complete graphs, which answers an open problem of Sheikholeslami and Volkmann (J. Comb. Optim., 2010) and completes a result in the same paper.     

Algorithm complexity of neighborhood total domination and $$(\rho ,\gamma _{nt})$$-graphs

A neighborhood total dominating set, abbreviated for NTD-set D, is a vertex set of G such that D is a dominating set with an extra property: the subgraph induced by the open neighborhood of D has no isolated vertex. The neighborhood total domination number, denoted by \(\gamma _{nt}(G)\), is the minimum cardinality of a NTD-set in G. In this paper, we prove that NTD problem is NP-complete for bipartite graphs and split graphs. Then we give a linear-time algorithm to determine \(\gamma _{nt}(T)\) for a given tree T. Finally, we characterize a constructive property of \((\gamma _{nt},2\gamma )\)-trees and provide a constructive characterization for \((\rho ,\gamma _{nt})\)-graphs, where \(\gamma \) and \(\rho \) are domination number and packing number for the given graph, respectively.     

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.     

On metric dimension of plane graphs with $$\frac{m}{2}$$ number of 10 sided faces

Journal of Combinatorial Optimization - Let $$\Gamma =\Gamma (V, E)$$ be a simple (multiple edges and loops are not considered), connected (every pair of distinct vertices are joined by a path),...     

2-Distance vertex-distinguishing index of subcubic graphs

This paper addresses the performance of scheduling algorithms for a two-stage no-wait hybrid flowshop environment with inter-stage flexibility, where there exist several parallel machines at each stage. Each job, composed of two operations, must be processed from start to completion without any interruption either on or between the two stages. For each job, the total processing time of its two operations is fixed, and the stage-1 operation is divided into two sub-parts: an obligatory part and an optional part (which is to be determined by a solution), with a constraint that no optional part of a job can be processed in parallel with an idleness of any stage-2 machine. The objective is to minimize the makespan. We prove that even for the special case with only one machine at each stage, this problem is strongly NP-hard. For the case with one machine at stage 1 and m machines at stage 2, we propose two polynomial time approximation algorithms with worst case ratio of \(3-\frac{2}{m+1}\) and \(2-\frac{1}{m+1}\), respectively. For the case with m machines at stage 1 and one machine at stage 2, we propose a polynomial time approximation algorithm with worst case ratio of 2. We also prove that all the worst case ratios are tight.     

The minimum value of geometric-arithmetic index of graphs with minimum degree 2

The geometric-arithmetic index was introduced in the chemical graph theory and it has shown to be applicable. The aim of this paper is to obtain the extremal graphs with respect to the geometric-arithmetic index among all graphs with minimum degree 2. Let G(2, n) be the set of connected simple graphs on n vertices with minimum degree 2. We use linear programming formulation and prove that the minimum value of the first geometric-arithmetic \((GA_{1})\) index of G(2, n) is obtained by the following formula:

$$\begin{aligned} GA_1^* = \left\{ \begin{array}{ll} n&{}\quad n \le 24, \\ \mathrm{{24}}\mathrm{{.79}}&{}\quad n = 25, \\ \frac{{4\left( {n - 2} \right) \sqrt{2\left( {n - 2} \right) } }}{n}&{}\quad n \ge 26. \\ \end{array} \right. \end{aligned}$$

     

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.     

Neighbor sum distinguishing index of 2-degenerate graphs

We consider proper edge colorings of a graph G using colors in \(\{1,\ldots ,k\}\). Such a coloring is called neighbor sum distinguishing if for each pair of adjacent vertices u and v, the sum of the colors of the edges incident with u is different from the sum of the colors of the edges incident with v. The smallest value of k in such a coloring of G is denoted by \({\mathrm ndi}_{\Sigma }(G)\). In this paper we show that if G is a 2-degenerate graph without isolated edges, then \({\mathrm ndi}_{\Sigma }(G)\le \max \{\Delta (G)+2,7\}\).     

Cha n nel assig nme n t problem a nd n-fold t-separa ted $$L(j_1,j_2,\ldo ts,j_m)$$-labeli ng of graphs

This paper considers the channel assignment problem in mobile communications systems. Suppose there are many base stations in an area, each of which demands a number of channels to transmit signals. The channels assigned to the same base station must be separated in some extension, and two channels assigned to two different stations that are within a distance must be separated in some other extension according to the distance between the two stations. The aim is to assign channels to stations so that the interference is controlled within an acceptable level and the spectrum of channels used is minimized. This channel assignment problem can be modeled as the multiple t-separated \(L(j_1,j_2,\ldots ,j_m)\)-labeling of the interference graph. In this paper, we consider the case when all base stations demand the same number of channels. This case is referred as n-fold t-separated \(L(j_1,j_2,\ldots ,j_m)\)-labeling of a graph. This paper first investigates the basic properties of n-fold t-separated \(L(j_1,j_2,\ldots ,j_m)\)-labelings of graphs. And then it focuses on the special case when \(m=1\). The optimal n-fold t-separated L(j)-labelings of all complete graphs and almost all cycles are constructed. As a consequence, the optimal n-fold t-separated \(L(j_1,j_2,\ldots ,j_m)\)-labelings of the triangular lattice and the square lattice are obtained for the case \(j_1=j_2=\cdots =j_m\). This provides an optimal solution to the corresponding channel assignment problems with interference graphs being the triangular lattice and the square lattice, in which each base station demands a set of n channels that are t-separated and channels from two different stations at distance at most m must be \(j_1\)-separated. We also study a variation of n-fold t-separated \(L(j_1,j_2,\ldots ,j_m)\)-labeling, namely, n-fold t-separated consecutive \(L(j_1,j_2,\ldots ,j_m)\)-labeling. And present the optimal n-fold t-separated consecutive L(j)-labelings of all complete graphs and cycles.     

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 total {k}-domination number of Cartesian products of graphs

Let γ _t ^{k}(G) denote the total {k}-domination number of graph G, and let denote the Cartesian product of graphs G and H. In this paper, we show that for any graphs G and H without isolated vertices, . As a corollary of this result, we have for all graphs G and H without isolated vertices, which is given by Pak Tung Ho (Util. Math., 2008, to appear) and first appeared as a conjecture proposed by Henning and Rall (Graph. Comb. 21:63–69, 2005). The work was supported by NNSF of China (No. 10701068 and No. 10671191).     

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

On (s,t)-relaxed L(2,1)-labeling of graphs

We initiate the study of relaxed \(L(2,1)\)-labelings of graphs. Suppose \(G\) is a graph. Let \(u\) be a vertex of \(G\). A vertex \(v\) is called an \(i\)-neighbor of \(u\) if \(d_G(u,v)=i\). A \(1\)-neighbor of \(u\) is simply called a neighbor of \(u\). Let \(s\) and \(t\) be two nonnegative integers. Suppose \(f\) is an assignment of nonnegative integers to the vertices of \(G\). If the following three conditions are satisfied, then \(f\) is called an \((s,t)\)-relaxed \(L(2,1)\)-labeling of \(G\): (1) for any two adjacent vertices \(u\) and \(v\) of \(G, f(u)\not =f(v)\); (2) for any vertex \(u\) of \(G\), there are at most \(s\) neighbors of \(u\) receiving labels from \(\{f(u)-1,f(u)+1\}\); (3) for any vertex \(u\) of \(G\), the number of \(2\)-neighbors of \(u\) assigned the label \(f(u)\) is at most \(t\). The minimum span of \((s,t)\)-relaxed \(L(2,1)\)-labelings of \(G\) is called the \((s,t)\)-relaxed \(L(2,1)\)-labeling number of \(G\), denoted by \(\lambda ^{s,t}_{2,1}(G)\). It is clear that \(\lambda ^{0,0}_{2,1}(G)\) is the so called \(L(2,1)\)-labeling number of \(G\). \(\lambda ^{1,0}_{2,1}(G)\) is simply written as \(\widetilde{\lambda }(G)\). This paper discusses basic properties of \((s,t)\)-relaxed \(L(2,1)\)-labeling numbers of graphs. For any two nonnegative integers \(s\) and \(t\), the exact values of \((s,t)\)-relaxed \(L(2,1)\)-labeling numbers of paths, cycles and complete graphs are determined. Tight upper and lower bounds for \((s,t)\)-relaxed \(L(2,1)\)-labeling numbers of complete multipartite graphs and trees are given. The upper bounds for \((s,1)\)-relaxed \(L(2,1)\)-labeling number of general graphs are also investigated. We introduce a new graph parameter called the breaking path covering number of a graph. A breaking path \(P\) is a vertex sequence \(v_1,v_2,\ldots ,v_k\) in which each \(v_i\) is adjacent to at least one vertex of \(v_{i-1}\) and \(v_{i+1}\) for \(i=2,3,\ldots ,k-1\). A breaking path covering of \(G\) is a set of disjoint such vertex sequences that cover all vertices of \(G\). The breaking path covering number of \(G\), denoted by \(bpc(G)\), is the minimum number of breaking paths in a breaking path covering of \(G\). In this paper, it is proved that \(\widetilde{\lambda }(G)= n+bpc(G^{c})-2\) if \(bpc(G^{c})\ge 2\) and \(\widetilde{\lambda }(G)\le n-1\) if and only if \(bpc(G^{c})=1\). The breaking path covering number of a graph is proved to be computable in polynomial time. Thus, if a graph \(G\) is of diameter two, then \(\widetilde{\lambda }(G)\) can be determined in polynomial time. Several conjectures and problems on relaxed \(L(2,1)\)-labelings are also proposed.     

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