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.     

The matching extension problem in general graphs is co-NP-complete

A simple connected graph G with 2n vertices is said to be k-extendable for an integer k with \(0<k<n\) if G contains a perfect matching and every matching of cardinality k in G is a subset of some perfect matching. Lakhal and Litzler (Inf Process Lett 65(1):11–16, 1998) discovered a polynomial algorithm that decides whether a bipartite graph is k-extendable. For general graphs, however, it has been an open problem whether there exists a polynomial algorithm. The new result presented in this paper is that the extendability problem is co-NP-complete.     

On the complete width and edge clique cover problems

A complete graph is the graph in which every two vertices are adjacent. For a graph \(G=(V,E)\), the complete width of G is the minimum k such that there exist k independent sets \(\mathtt {N}_i\subseteq V\), \(1\le i\le k\), such that the graph \(G'\) obtained from G by adding some new edges between certain vertices inside the sets \(\mathtt {N}_i\), \(1\le i\le k\), is a complete graph. The complete width problem is to decide whether the complete width of a given graph is at most k or not. In this paper we study the complete width problem. We show that the complete width problem is NP-complete on \(3K_2\)-free bipartite graphs and polynomially solvable on \(2K_2\)-free bipartite graphs and on \((2K_2,C_4)\)-free graphs. As a by-product, we obtain the following new results: the edge clique cover problem is NP-complete on \(\overline{3K_2}\)-free co-bipartite graphs and polynomially solvable on \(C_4\)-free co-bipartite graphs and on \((2K_2, C_4)\)-free graphs. We also give a characterization for k-probe complete graphs which implies that the complete width problem admits a kernel of at most \(2^k\) vertices. This provides another proof for the known fact that the edge clique cover problem admits a kernel of at most \(2^k\) vertices. Finally we determine all graphs of small complete width \(k\le 3\).     

On the coefficients of the independence polynomial of graphs

An independent set of a graph G is a set of pairwise non-adjacent vertices. Let \(i_k = i_k(G)\) be the number of independent sets of cardinality k of G. The independence polynomial \(I(G, x)=\sum _{k\geqslant 0}i_k(G)x^k\) defined first by Gutman and Harary has been the focus of considerable research recently, whereas \(i(G)=I(G, 1)\) is called the Merrifield–Simmons index of G. In this paper, we first proved that among all trees of order n,  the kth coefficient \(i_k\) is smallest when the tree is a path, and is largest for star. Moreover, the graph among all trees of order n with diameter at least d whose all coefficients of I(G, x) are largest is identified. Then we identify the graphs among the n-vertex unicyclic graphs (resp. n-vertex connected graphs with clique number \(\omega \)) which simultaneously minimize all coefficients of I(G, x), whereas the opposite problems of simultaneously maximizing all coefficients of I(G, x) among these two classes of graphs are also solved respectively. At last we characterize the graph among all the n-vertex connected graph with chromatic number \(\chi \) (resp. vertex connectivity \(\kappa \)) which simultaneously minimize all coefficients of I(G, x). Our results may deduce some known results on Merrifield–Simmons index of graphs.     

Modified linear programming and class 0 bounds for graph pebbling

Given a configuration of pebbles on the vertices of a connected graph G, a pebbling move removes two pebbles from some vertex and places one pebble on an adjacent vertex. The pebbling number of a graph G is the smallest integer k such that for each vertex v and each configuration of k pebbles on G there is a sequence of pebbling moves that places at least one pebble on v. First, we improve on results of Hurlbert, who introduced a linear optimization technique for graph pebbling. In particular, we use a different set of weight functions, based on graphs more general than trees. We apply this new idea to some graphs from Hurlbert’s paper to give improved bounds on their pebbling numbers. Second, we investigate the structure of Class 0 graphs with few edges. We show that every n-vertex Class 0 graph has at least \(\frac{5}{3}n - \frac{11}{3}\) edges. This disproves a conjecture of Blasiak et al. For diameter 2 graphs, we strengthen this lower bound to \(2n - 5\), which is best possible. Further, we characterize the graphs where the bound holds with equality and extend the argument to obtain an identical bound for diameter 2 graphs with no cut-vertex.     

The <Emphasis Type="Italic">k</Emphasis>-hop connected dominating set problem: approximation and hardness

Let G be a connected graph and k be a positive integer. A vertex subset D of G is a k-hop connected dominating set if the subgraph of G induced by D is connected, and for every vertex v in G there is a vertex u in D such that the distance between v and u in G is at most k. We study the problem of finding a minimum k-hop connected dominating set of a graph (\({\textsc {Min}}k{\hbox {-}\textsc {CDS}}\)). We prove that \({\textsc {Min}}k{\hbox {-}\textsc {CDS}}\) is \(\mathscr {NP}\)-hard on planar bipartite graphs of maximum degree 4. We also prove that \({\textsc {Min}}k{\hbox {-}\textsc {CDS}}\) is \(\mathscr {APX}\)-complete on bipartite graphs of maximum degree 4. We present inapproximability thresholds for \({\textsc {Min}}k{\hbox {-}\textsc {CDS}}\) on bipartite and on (1, 2)-split graphs. Interestingly, one of these thresholds is a parameter of the input graph which is not a function of its number of vertices. We also discuss the complexity of computing this graph parameter. On the positive side, we show an approximation algorithm for \({\textsc {Min}}k{\hbox {-}\textsc {CDS}}\). Finally, when \(k=1\), we present two new approximation algorithms for the weighted version of the problem restricted to graphs with a polynomially bounded number of minimal separators.     

A simpler PTAS for connected <Emphasis Type="Italic">k</Emphasis>-path vertex cover in homogeneous wireless sensor network

Because of its application in the field of security in wireless sensor networks, k-path vertex cover (\(\hbox {VCP}_k\)) has received a lot of attention in recent years. Given a graph \(G=(V,E)\), a vertex set \(C\subseteq V\) is a k-path vertex cover (\(\hbox {VCP}_k\)) of G if every path on k vertices has at least one vertex in C, and C is a connected k-path vertex cover of G (\(\hbox {CVCP}_k\)) if furthermore the subgraph of G induced by C is connected. A homogeneous wireless sensor network can be modeled as a unit disk graph. This paper presents a new PTAS for \(\hbox {MinCVCP}_k\) on unit disk graphs. Compared with previous PTAS given by Liu et al., our method not only simplifies the algorithm and reduces the time-complexity, but also simplifies the analysis by a large amount.     

On computing a minimum secure dominating set in block graphs

In a graph \(G=(V,E)\), a set \(D \subseteq V\) is said to be a dominating set of G if for every vertex \(u\in V{\setminus }D\), there exists a vertex \(v\in D\) such that \(uv\in E\). A secure dominating set of the graph G is a dominating set D of G such that for every \(u\in V{\setminus }D\), there exists a vertex \(v\in D\) such that \(uv\in E\) and \((D{\setminus }\{v\})\cup \{u\}\) is a dominating set of G. Given a graph G and a positive integer k, the secure domination problem is to decide whether G has a secure dominating set of cardinality at most k. The secure domination problem has been shown to be NP-complete for chordal graphs via split graphs and for bipartite graphs. In Liu et al. (in: Proceedings of 27th workshop on combinatorial mathematics and computation theory, 2010), it is asked to find a polynomial time algorithm for computing a minimum secure dominating set in a block graph. In this paper, we answer this by presenting a linear time algorithm to compute a minimum secure dominating set in block graphs. We then strengthen the known NP-completeness of the secure domination problem by showing that the secure domination problem is NP-complete for undirected path graphs and chordal bipartite graphs.     

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.     

On the b-coloring of tight graphs

A coloring c of a graph \(G=(V,E)\) is a b -coloring if for every color i there is a vertex, say w(i), of color i whose neighborhood intersects every other color class. The vertex w(i) is called a b-dominating vertex of color i. The b -chromatic number of a graph G, denoted by b(G), is the largest integer k such that G admits a b-coloring with k colors. Let m(G) be the largest integer m such that G has at least m vertices of degree at least \(m-1\). A graph G is tight if it has exactly m(G) vertices of degree \(m(G)-1\), and any other vertex has degree at most \(m(G)-2\). In this paper, we show that the b-chromatic number of tight graphs with girth at least 8 is at least \(m(G)-1\) and characterize the graphs G such that \(b(G)=m(G)\). Lin and Chang (2013) conjectured that the b-chromatic number of any graph in \(\mathcal {B}_{m}\) is m or \(m-1\) where \(\mathcal {B}_{m}\) is the class of tight bipartite graphs \((D,D{^\prime })\) of girth 6 such that D is the set of vertices of degree \(m-1\). We verify the conjecture of Lin and Chang for some subclass of \(\mathcal {B}_{m}\), and we give a lower bound for any graph in \(\mathcal {B}_{m}\).     

Total edge irregularity strength of accordion graphs

An edge irregular total k-labeling \(\varphi : V\cup E \rightarrow \{ 1,2, \dots , k \}\) of a graph \(G=(V,E)\) is a labeling of vertices and edges of G in such a way that for any different edges xy and \(x'y'\) their weights \(\varphi (x)+ \varphi (xy) + \varphi (y)\) and \(\varphi (x')+ \varphi (x'y') + \varphi (y')\) are distinct. The total edge irregularity strength, tes(G), is defined as the minimum k for which G has an edge irregular total k-labeling. We have determined the exact value of the total edge irregularity strength of accordion graphs.     

Reconfiguration of dominating sets

We explore a reconfiguration version of the dominating set problem, where a dominating set in a graph G is a set S of vertices such that each vertex is either in S or has a neighbour in S. In a reconfiguration problem, the goal is to determine whether there exists a sequence of feasible solutions connecting given feasible solutions s and t such that each pair of consecutive solutions is adjacent according to a specified adjacency relation. Two dominating sets are adjacent if one can be formed from the other by the addition or deletion of a single vertex. For various values of k, we consider properties of \(D_k(G)\), the graph consisting of a node for each dominating set of size at most k and edges specified by the adjacency relation. Addressing an open question posed by Haas and Seyffarth, we demonstrate that \(D_{\varGamma (G)+1}(G)\) is not necessarily connected, for \(\varGamma (G)\) the maximum cardinality of a minimal dominating set in G. The result holds even when graphs are constrained to be planar, of bounded tree-width, or b-partite for \(b \ge 3\). Moreover, we construct an infinite family of graphs such that \(D_{\gamma (G)+1}(G)\) has exponential diameter, for \(\gamma (G)\) the minimum size of a dominating set. On the positive side, we show that \(D_{n-\mu }(G)\) is connected and of linear diameter for any graph G on n vertices with a matching of size at least \(\mu +1\).     

On maximum Wiener index of trees and graphs with given radius

Let G be a connected graph of order n. The long-standing open and close problems in distance graph theory are: what is the Wiener index W(G) or average distance \(\mu (G)\) among all graphs of order n with diameter d (radius r)? There are very few number of articles where were worked on the relationship between radius or diameter and Wiener index. In this paper, we give an upper bound on Wiener index of trees and graphs in terms of number of vertices n, radius r, and characterize the extremal graphs. Moreover, from this result we give an upper bound on \(\mu (G)\) in terms of order and independence number of graph G. Also we present another upper bound on Wiener index of graphs in terms of number of vertices n, radius r and maximum degree \(\Delta \), and characterize the extremal graphs.     

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 algorithmic aspects of strong subcoloring

A partition of the vertex set V(G) of a graph G into \(V(G)=V_1\cup V_2\cup \cdots \cup V_k\) is called a k-strong subcoloring if \(d(x,y)\ne 2\) in G for every \(x,y\in V_i\), \(1\le i \le k\) where d(x, y) denotes the length of a shortest x-y path in G. The strong subchromatic number is defined as \(\chi _{sc}(G)=\text {min}\{ k:G \text { admits a }k\)-\(\text {strong subcoloring}\}\). In this paper, we explore the complexity status of the StrongSubcoloring problem: for a given graph G and a positive integer k, StrongSubcoloring is to decide whether G admits a k-strong subcoloring. We prove that StrongSubcoloring is NP-complete for subcubic bipartite graphs and the problem is polynomial time solvable for trees. In addition, we prove the following dichotomy results: (i) for the class of \(K_{1,r}\)-free split graphs, StrongSubcoloring is in P when \(r\le 3\) and NP-complete when \(r>3\) and (ii) for the class of H-free graphs, StrongSubcoloring is polynomial time solvable only if H is an induced subgraph of \(P_4\); otherwise the problem is NP-complete. Next, we consider a lower bound on the strong subchromatic number. A strong set is a set S of vertices of a graph G such that for every \(x,y\in S\), \(d(x,y)= 2\) in G and the cardinality of a maximum strong set in G is denoted by \(\alpha _{s}(G)\). Clearly, \(\alpha _{s}(G)\le \chi _{sc}(G)\). We consider the complexity status of the StrongSet problem: given a graph G and a positive integer k, StrongSet asks whether G contains a strong set of cardinality k. We prove that StrongSet is NP-complete for (i) bipartite graphs and (ii) \(K_{1,4}\)-free split graphs, and it is polynomial time solvable for (i) trees and (ii) \(P_4\)-free graphs.     

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.     

Improved floor-planning of graphs via adjacency-preserving transformations

Let G=(V,E) and G′=(V′,E′) be two graphs, an adjacency-preserving transformation from G to G′ is a one-to-many and onto mapping from V to V′ satisfying the following: (1) Each vertex v∈V in G is mapped to a non-empty subset \(\mathcal{A}(v)\subset V'\) in G′. The subgraph induced by \(\mathcal{A}(v)\) is a connected subgraph of G′; (2) if u≠v∈V, then \(\mathcal{A}(u)\cap\mathcal{A}(v)=\emptyset\); and (3) two vertices u and v are adjacent to each other in G if and only if subgraphs induced by \(\mathcal{A}(u)\) and \(\mathcal{A}(v)\) are connected in G′.In this paper, we study adjacency-preserving transformations from plane triangulations to irreducible triangulations (which are internally triangulated, with four exterior vertices and no separating triangles). As one shall see, our transformations not only preserve adjacency well, but also preserve the endowed realizers of plane triangulations well in the endowed transversal structures of the image irreducible triangulations, which may be desirable in some applications.We then present such an application in floor-planning of plane graphs. The expected grid size of the floor-plan of our linear time algorithm is improved to \((\frac{5n}{8}+O(1))\times (\frac{23n}{24}+O(1))\), though the worst case grid size bound of the algorithm remains \(\lfloor\frac{2n+1}{3}\rfloor\times(n-1)\), which is the same as the algorithm presented in Liao et al. (J. Algorithms 48:441–451, 2003).     

On the vertex cover $$P_3$$ problem parameterized by treewidth

Consider a graph G. A subset of vertices, F, is called a vertex cover \(P_t\) (\(VCP_t\)) set if every path of order t contains at least one vertex in F. Finding a minimum \(VCP_t\) set in a graph is is NP-hard for any integer \(t\ge 2\) and is called the \(MVCP_3\) problem. In this paper, we study the parameterized algorithms for the \(MVCP_3\) problem when the underlying graph G is parameterized by the treewidth. Given an n-vertex graph together with its tree decomposition of width at most p, we present an algorithm running in time \(4^{p}\cdot n^{O(1)}\) for the \(MVCP_3\) problem. Moreover, we show that for the \(MVCP_3\) problem on planar graphs, there is a subexponential parameterized algorithm running in time \(2^{O(\sqrt{k})}\cdot n^{O(1)}\) where k is the size of the optimal solution.     

First-Fit colorings of graphs with no cycles of a prescribed even length

The First-Fit (or Grundy) chromatic number of a graph G denoted by \(\chi _{{_\mathsf{FF}}}(G)\), is the maximum number of colors used by the First-Fit (greedy) coloring algorithm when applied to G. In this paper we first show that any graph G contains a bipartite subgraph of Grundy number \(\lfloor \chi _{{_\mathsf{FF}}}(G) /2 \rfloor +1\). Using this result we prove that for every \(t\ge 2\) there exists a real number \(c>0\) such that in every graph G on n vertices and without cycles of length 2t, any First-Fit coloring of G uses at most \(cn^{1/t}\) colors. It is noted that for \(t=2\) this bound is the best possible. A compactness conjecture is also proposed concerning the First-Fit chromatic number involving the even girth of graphs.     

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.