Paired-domination in generalized claw-free graphs

In this paper, we continue the study of paired-domination in graphs introduced by Haynes and Slater (Networks 32 (1998) 199–206). A set S of vertices in a graph G is a paired-dominating set of G if every vertex of G is adjacent to some vertex in S and if the subgraph induced by S contains a perfect matching. The paired-domination number of G, denoted by , is the minimum cardinality of a paired-dominating set of G. If G does not contain a graph F as an induced subgraph, then G is said to be F-free. Haynes and Slater (Networks 32 (1998) 199–206) showed that if G is a connected graph of order , then and this bound is sharp for graphs of arbitrarily large order. Every graph is -free for some integer a ≥ 0. We show that for every integer a ≥ 0, if G is a connected -free graph of order n ≥ 2, then with infinitely many extremal graphs.     

Parameterized dominating set problem in chordal graphs: complexity and lower bound

In this paper, we study the parameterized dominating set problem in chordal graphs. The goal of the problem is to determine whether a given chordal graph G=(V,E) contains a dominating set of size k or not, where k is an integer parameter. We show that the problem is W[1]-hard and it cannot be solved in time unless 3SAT can be solved in subexponential time. In addition, we show that the upper bound of this problem can be improved to when the underlying graph G is an interval graph.     

Anti-forcing spectra of perfect matchings of graphs

Let M be a perfect matching of a graph G. The smallest number of edges whose removal to make M as the unique perfect matching in the resulting subgraph is called the anti-forcing number of M. The anti-forcing spectrum of G is the set of anti-forcing numbers of all perfect matchings in G, denoted by \(\hbox {Spec}_{af}(G)\). In this paper, we show that any finite set of positive integers can be the anti-forcing spectrum of a graph. We present two classes of hexagonal systems whose anti-forcing spectra are integer intervals. Finally, we show that determining the anti-forcing number of a perfect matching of a bipartite graph with maximum degree four is a NP-complete problem.     

Partitioning 2-edge-colored complete multipartite graphs into monochromatic cycles, paths and trees

In this paper we consider the problem of partitioning complete multipartite graphs with edges colored by 2 colors into the minimum number of vertex disjoint monochromatic cycles, paths and trees, respectively. For general graphs we simply address the decision version of these three problems the 2-PGMC, 2-PGMP and 2-PGMT problems, respectively. We show that both 2-PGMC and 2-PGMP problems are NP-complete for complete multipartite graphs and the 2-PGMT problem is NP-complete for bipartite graphs. This also implies that all these three problems are NP-complete for general graphs, which solves a question proposed by the authors in a previous paper. Nevertheless, we show that the 2-PGMT problem can be solved in polynomial time for complete multipartite graphs. Research supported by NSFC.     

Tagged Probe Interval Graphs

A generalization of interval graph is introduced for cosmid contig mapping of DNA. A graph is a tagged probe interval graph if its vertex set can be partitioned into two subsets of probes and nonprobes, and a closed interval can be assigned to each vertex such that two vertices are adjacent if and only if at least one of them is a probe and one end of its corresponding interval is contained in the interval corresponding to the other vertex. We show that tagged probe interval graphs are weakly triangulated graphs, hence are perfect graphs. For a tagged probe interval graph with a given partition, we give a chordal completion that is consistent to any interval completions with respect to the same vertex partition.     

Necessary Edges in k-Chordalisations of Graphs

A k-chordalisation of a graph G = (V,E) is a graph H = (V,F) obtained by adding edges to G, such that H is a chordal graph with maximum clique size at most k. This note considers the problem: given a graph G = (V,E) which pairs of vertices, non-adjacent in G, will be an edge in every k-chordalisation of G. Such a pair is called necessary for treewidth k. An equivalent formulation is: which edges can one add to a graph G such that every tree decomposition of G of width at most k is also a tree decomposition of the resulting graph G. Some sufficient, and some necessary and sufficient conditions are given for pairs of vertices to be necessary for treewidth k. For a fixed k, one can find in linear time for a given graph G the set of all necessary pairs for treewidth k. If k is given as part of the input, then this problem is coNP-hard. A few similar results are given when interval graphs (and hence pathwidth) are used instead of chordal graphs and treewidth.     

Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs

A k-colouring of a graph G=(V,E) is a mapping c:V→{1,2,…,k} such that c(u)≠c(v) whenever uv is an edge. The reconfiguration graph of the k-colourings of G contains as its vertex set the k-colourings of G, and two colourings are joined by an edge if they differ in colour on just one vertex of G. We introduce a class of k-colourable graphs, which we call k-colour-dense graphs. We show that for each k-colour-dense graph G, the reconfiguration graph of the ?-colourings of G is connected and has diameter O(|V|²), for all ?≥k+1. We show that this graph class contains the k-colourable chordal graphs and that it contains all chordal bipartite graphs when k=2. Moreover, we prove that for each k≥2 there is a k-colourable chordal graph G whose reconfiguration graph of the (k+1)-colourings has diameter Θ(|V|²).     

The thickness of the complete multipartite graphs and the join of graphs

The thickness of a graph is the minimum number of planar spanning subgraphs into which the graph can be decomposed. It is known for relatively few classes of graphs, compared to other topological invariants, e.g., genus and crossing number. For the complete bipartite graphs, Beineke et al. (Proc Camb Philos Soc 60:1–5, 1964) gave the answer for most graphs in this family in 1964. In this paper, we derive formulas and bounds for the thickness of some complete k-partite graphs. And some properties for the thickness for the join of two graphs are also obtained.     

Even factors of graphs

An even factor of a graph is a spanning subgraph in which each vertex has a positive even degree. Favaron and Kouider (J Gr Theory 77:58–67, 2014) showed that if a simple graph G has an even factor, then it has an even factor F with \(|E(F)| \ge \frac{7}{16} (|E(G)| + 1)\). This ratio was improved to \(\frac{4}{7}\) recently by  Chen and Fan (J Comb Theory Ser B 119:237–244, 2016), which is the best possible. In this paper, we take the set of vertices of degree 2 (say \(V_{2}(G)\)) into consideration and further strengthen this lower bound. Our main result is to show that for any simple graph G having an even factor, G has an even factor F with \(|E(F)| \ge \frac{4}{7} (|E(G)| + 1)+\frac{1}{7}|V_{2}(G)|\).     

Recognition of overlap graphs

Overlap graphs occur in computational biology and computer science, and have applications in genome sequencing, string compression, and machine scheduling. Given two strings \(s_{i}\) and \(s_{j}\) , their overlap string is defined as the longest string \(v\) such that \(s_{i} = uv\) and \(s_{j} = vw\) , for some non empty strings \(u,w\) , and its length is called the overlap between these two strings. A weighted directed graph is an overlap graph if there exists a set of strings with one-to-one correspondence to the vertices of the graph, such that each arc weight in the graph equals the overlap between the corresponding strings. In this paper, we characterize the class of overlap graphs, and we present a polynomial time recognition algorithm as a direct consequence. Given a weighted directed graph \(G\) , the algorithm constructs a set of strings that has \(G\) as its overlap graph, or decides that this is not possible.     

Degree-constrained orientations of embedded graphs

We investigate the problem of orienting the edges of an embedded graph in such a way that the resulting digraph fulfills given in-degree specifications both for the vertices and for the faces of the embedding. This primal-dual orientation problem was first proposed by Frank for the case of planar graphs, in conjunction with the question for a good characterization of the existence of such orientations. We answer this question by showing that a feasible orientation of a planar embedding, if it exists, can be constructed by combining certain parts of a primally feasible orientation and a dually feasible orientation. For the general case of arbitrary embeddings, we show that the number of feasible orientations is bounded by \(2^{2g}\), where \(g\) is the genus of the embedding. Our proof also yields a fixed-parameter algorithm for determining all feasible orientations parameterized by the genus. In contrast to these positive results, however, we also show that the problem becomes \(N\!P\)-complete even for a fixed genus if only upper and lower bounds on the in-degrees are specified instead of exact values.     

On backbone coloring of graphs

Let G be a graph and H a subgraph of G. A backbone-k-coloring of (G,H) is a mapping f: V(G)→{1,2,…,k} such that |f(u)−f(v)|≥2 if uv∈E(H) and |f(u)−f(v)|≥1 if uv∈E(G)\E(H). The backbone chromatic number of (G,H) is the smallest integer k such that (G,H) has a backbone-k-coloring. In this paper, we characterize the backbone chromatic number of Halin graphs G=T∪C with respect to given spanning trees T. Also we study the backbone coloring for other special graphs such as complete graphs, wheels, graphs with small maximum average degree, graphs with maximum degree 3, etc.     

An Approximation Scheme for Bin Packing with Conflicts

In this paper we consider the following bin packing problem with conflicts. Given a set of items V = {1,..., n} with sizes s₁,..., s (0,1) and a conflict graph G = (V, E), we consider the problem to find a packing for the items into bins of size one such that adjacent items (j, j) E are assigned to different bins. The goal is to find an assignment with a minimum number of bins. This problem is a natural generalization of the classical bin packing problem.We propose an asymptotic approximation scheme for the bin packing problem with conflicts restricted to d-inductive graphs with constant d. This graph class contains trees, grid graphs, planar graphs and graphs with constant treewidth. The algorithm finds an assignment for the items such that the generated number of bins is within a factor of (1 + ) of optimal provided that the optimum number is sufficiently large. The running time of the algorithm is polynomial both in n and in .     

Fractional matching preclusion of graphs

Let F be an edge subset and \(F^{\prime }\) a subset of edges and vertices of a graph G. If \(G-F\) and \(G-F^{\prime }\) have no fractional perfect matchings, then F is a fractional matching preclusion (FMP) set and \(F^{\prime }\) is a fractional strong MP (FSMP) set of G. The FMP (FSMP) number of G is the minimum size of FMP (FSMP) sets of G. In this paper, the FMP number and the FSMP number of Petersen graph, complete graphs and twisted cubes are obtained, respectively.     

Minimum choosability of planar graphs

The problem of list coloring of graphs appears in practical problems concerning channel or frequency assignment. In this paper, we study the minimum number of choosability of planar graphs. A graph G is edge-k-choosable if whenever every edge x is assigned with a list of at least k colors, L(x)), there exists an edge coloring \(\phi \) such that \(\phi (x) \in L(x)\). Similarly, A graph G is toal-k-choosable if when every element (edge or vertex) x is assigned with a list of at least k colors, L(x), there exists an total coloring \(\phi \) such that \(\phi (x) \in L(x)\). We proved \(\chi '_{l}(G)=\Delta \) and \(\chi ''_{l}(G)=\Delta +1\) for a planar graph G with maximum degree \(\Delta \ge 8\) and without chordal 6-cycles, where the list edge chromatic number \(\chi '_{l}(G)\) of G is the smallest integer k such that G is edge-k-choosable and the list total chromatic number \(\chi ''_{l}(G)\) of G is the smallest integer k such that G is total-k-choosable.     

Wide diameters of de Bruijn graphs

The wide diameter of a graph is an important parameter to measure fault-tolerance of interconnection network. This paper proves that for any two vertices in de Bruijn undirected graph UB(d,n), there are 2d−2 internally disjoint paths of length at most 2n+1. Therefore, the (2d−2)-wide diameter of UB(d,n) is not greater than 2n+1. Dedicated to Professor Frank K. Hwang on the occasion of his sixty fifth birthday.     

Rainbow connection numbers of Cayley graphs

An edge colored graph is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection number, rc-number for short, of a graph \({\varGamma }\), is the smallest number of colors that are needed in order to make \({\varGamma }\) rainbow connected. In this paper, we give a method to bound the rc-numbers of graphs with certain structural properties. Using this method, we investigate the rc-numbers of Cayley graphs, especially, those defined on abelian groups and on dihedral groups.     

Coupon coloring of some special graphs

Let G be a graph without isolated vertices. A k-coupon coloring of G is a k-coloring of G such that the neighborhood of every vertex of G contains vertices of all colors from \([k] =\{1, 2, \ldots , k\}\), which was recently introduced by Chen, Kim, Tait and Verstraete. The coupon coloring number \(\chi _c(G)\) of G is the maximum k for which a k-coupon coloring exists. In this paper, we mainly study the coupon coloring of some special classes of graphs. We determine the coupon coloring numbers of complete graphs, complete k-partite graphs, wheels, cycles, unicyclic graphs, bicyclic graphs and generalised \(\Theta \)-graphs.     

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.     

2-Distance paired-dominating number of graphs

Let \(G=(V,E)\) be a simple graph without isolated vertices. For a positive integer \(k\) , a subset \(D\) of \(V(G)\) is a \(k\) -distance paired-dominating set if each vertex in \(V\setminus {D}\) is within distance \(k\) of a vertex in \(D\) and the subgraph induced by \(D\) contains a perfect matching. In this paper, we give some upper bounds on the 2-distance paired-dominating number in terms of the minimum and maximum degree, girth, and order.