Shifting strategy for geometric graphs without?geometry

We give a simple framework which is an alternative to the celebrated and widely used shifting strategy of Hochbaum and Maass (J. ACM 32(1):103?C136, 1985) which has yielded efficient algorithms with good approximation bounds for numerous optimization problems in low-dimensional Euclidean space. Our framework does not require the input graph/metric to have a geometric realization??it only requires that the input graph satisfy some weak property referred to as growth boundedness. Growth bounded graphs form an important graph class that has been used to model wireless networks. We show how to apply the framework to obtain a polynomial time approximation scheme (PTAS) for the maximum (weighted) independent set problem on this important graph class; the problem is W[1]-complete. Via a more sophisticated application of our framework, we show how to obtain a PTAS for the maximum (weighted) independent set for intersection graphs of (low-dimensional) fat objects that are expressed without geometry. Erlebach et al. (SIAM J. Comput. 34(6):1302?C1323, 2005) and Chan (J. Algorithms 46(2):178?C189, 2003) independently gave a PTAS for maximum weighted independent set problem for intersection graphs of fat geometric objects, say ball graphs, which required a geometric representation of the input. Our result gives a positive answer to a question of Erlebach et al. (SIAM J. Comput. 34(6):1302?C1323, 2005) who asked if a PTAS for this problem can be obtained without access to a geometric representation.     

Independent dominating sets in regular graphs

Let G be a simple, regular graph of order n and degree δ. The independent domination number i(G) is defined to be the minimum cardinality among all maximal independent sets of vertices of G. We establish new upper bounds, as functions of n and δ, for the independent domination number of regular graphs with $n/6<\delta< (3-\sqrt{5})n/2$ . Our two main theorems complement recent results of Goddard et al. (Ann. Comb., 2011) for larger values of δ.     

Path packing and a related optimization problem

Let G be a supply graph, with the node set N and edge set E, and (T,S) be a demand graph, with T?N, S∩E=?. Observe paths whose end-vertices form pairs in S (called S-paths). The following path packing problem for graphs is fundamental: what is the maximal number of S-paths in G? In this paper this problem is studied under two assumptions: (a) the node degrees in N?T are even, and (b) any three distinct pairwise intersecting maximal stable sets A,B,C of (T,S) satisfy A∩B=B∩C=A∩C (this condition was defined by A. Karzanov in Linear Algebra Appl. 114–115:293–328, 1989). For any demand graph violating (b) the problem is known to be NP-hard even under (a), and only a few cases satisfying (a) and (b) have been solved. In each of the solved cases, a solution and an optimal dual object were defined by a certain auxiliary “weak” multiflow optimization problem whose solutions supply constructive elements for S-paths and concatenate them into an S-path packing by a kind of matching. In this paper the above approach is extended to all demand graphs satisfying (a) and (b), by proving existence of a common solution of the S-path packing and its weak counterpart. The weak problem is very interesting for its own sake, and has connections with such topics as Mader’s edge-disjoint path packing theorem and b-factors in graphs.     

A linear-time algorithm for clique-coloring problem in circular-arc graphs

A maximal clique of G is a clique not properly contained in any other clique. A k-clique-coloring of a graph G is an assignment of k colors to the vertices of G such that no maximal clique with at least two vertices is monochromatic. The smallest integer k admitting a k-clique-coloring of G is called clique-coloring number of G. Cerioli and Korenchendler (Electron Notes Discret Math 35:287–292, 2009) showed that there is a polynomial-time algorithm to solve the clique-coloring problem in circular-arc graphs and asked whether there exists a linear-time algorithm to find an optimal clique-coloring in circular-arc graphs or not. In this paper we present a linear-time algorithm of the optimal clique-coloring in circular-arc graphs.     

Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipartite graphs

A set D?V of a graph G=(V,E) is a dominating set of G if every vertex in V?D has at least one neighbor in D. A dominating set D of G is a paired-dominating set of G if the induced subgraph, G[D], has a perfect matching. Given a graph G=(V,E) and a positive integer k, the paired-domination problem is to decide whether G has a paired-dominating set of cardinality at most k. The paired-domination problem is known to be NP-complete for bipartite graphs. In this paper, we, first, strengthen this complexity result by showing that the paired-domination problem is NP-complete for perfect elimination bipartite graphs. We, then, propose a linear time algorithm to compute a minimum paired-dominating set of a chordal bipartite graph, a well studied subclass of bipartite graphs.     

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.     

On the total outer-connected domination in graphs

A set S of vertices of a graph G is a total outer-connected dominating set if every vertex in V(G) is adjacent to some vertex in S and the subgraph induced by V?S is connected. The total outer-connected domination number γ _toc (G) is the minimum size of such a set. We give some properties and bounds for γ _toc in general graphs and in trees. For graphs of order n, diameter 2 and minimum degree at least 3, we show that $\gamma_{toc}(G)\le \frac{2n-2}{3}$ and we determine the extremal graphs.     

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.     

Sharp bounds of the Zagreb indices of k-trees

For a graph G, the first Zagreb index M ₁ is equal to the sum of squares of the vertex degrees, and the second Zagreb index M ₂ is equal to the sum of the products of degrees of pairs of adjacent vertices. The Zagreb indices have been the focus of considerable research in computational chemistry dating back to Gutman and Trinajsti? in 1972. In 2004, Das and Gutman determined sharp upper and lower bounds for M ₁ and M ₂ values for trees along with the unique trees that obtain the minimum and maximum M ₁ and M ₂ values respectively. In this paper, we generalize the results of Das and Gutman to the generalized tree, the k-tree, where the results of Das and Gutman are for k=1. Also by showing that maximal outerplanar graphs are 2-trees, we also extend a result of Hou, Li, Song, and Wei who determined sharp upper and lower bounds for M ₁ and M ₂ values for maximal outerplanar graphs.     

Generalized perfect domination in graphs

Let k be a positive integer and G=(V,E) be a graph. A vertex subset D of a graph G is called a perfect k-dominating set of G, if every vertex v of G, not in D, is adjacent to exactly k vertices of D. The minimum cardinality of a perfect k-dominating set of G is the perfect k-domination number γ _kp (G). In this paper, we give characterizations of graphs for which γ _kp (G)=γ(G)+k?2 and prove that the perfect k-domination problem is NP-complete even when restricted to bipartite graphs and chordal graphs. Also, by using dynamic programming techniques, we obtain an algorithm to determine the perfect k-domination number of trees.     

k-tuple total domination in cross products of graphs

For k??1 an integer, a set S of vertices in a graph G with minimum degree at least?k is a k-tuple total dominating set of G if every vertex of G is adjacent to at least k vertices in S. The minimum cardinality of a k-tuple total dominating set of G is the k-tuple total domination number of G. When k=1, the k-tuple total domination number is the well-studied total domination number. In this paper, we establish upper and lower bounds on the k-tuple total domination number of the cross product graph G×H for any two graphs G and H with minimum degree at least?k. In particular, we determine the exact value of the k-tuple total domination number of the cross product of two complete graphs.     

Improved approximation for spanning star forest in dense graphs

A spanning subgraph of a graph G is called a spanning star forest of G if it is a collection of node-disjoint trees of depth at most 1. The size of a spanning star forest is the number of leaves in all its components. The goal of the spanning star forest problem is to find the maximum-size spanning star forest of a given graph. In this paper, we study the spanning star forest problem on c-dense graphs, where for any fixed c∈(0,1), a graph of n vertices is called c-dense if it contains at least cn ²/2 edges. We design a $(\alpha+(1-\alpha)\sqrt{c}-\epsilon)$ -approximation algorithm for spanning star forest in c-dense graphs for any ?>0, where $\alpha=\frac{193}{240}$ is the best known approximation ratio of the spanning star forest problem in general graphs. Thus, our approximation ratio outperforms the best known bound for this problem when dealing with c-dense graphs. We also prove that, for any constant c∈(0,1), approximating spanning star forest in c-dense graphs is APX-hard. We then demonstrate that for weighted versions (both node- and edge-weighted) of this problem, we cannot get any approximation algorithm with strictly better performance guarantee on c-dense graphs than on general graphs. Finally, we give strong inapproximability results for a closely related problem, namely the minimum dominating set problem, restricted on c-dense graphs.     

Independent dominating sets in triangle-free graphs

The independent domination number of a graph is the smallest cardinality of an independent set that dominates the graph. In this paper we consider the independent domination number of triangle-free graphs. We improve several of the known bounds as a function of the order and minimum degree, thereby answering conjectures of Haviland.     

A refined algorithm for maximum independent set in degree-4 graphs

The maximum independent set problem is one of the most important problems in theoretical analysis on time and space complexities of exact algorithms. Theoretical improvement on upper bounds on time complexity to solve this problem in low-degree graphs can lead to an improvement on that to the problem in general graphs. In this paper, we derive an upper bound \(O^*(1.1376^n)\) on the time complexity of a polynomial-space algorithm that solves the maximum independent set problem in an n-vertex graph with degree bounded by 4, improving all previous upper bounds on the time complexity of exact algorithms to this problem. Our algorithm is a branch-and-reduce algorithm and analyzed by using the measure-and-conquer method. To make an amortized analysis of the running time bound, we use an idea of “shift” to save some decrease of the measure from good branches to bad branches. Our algorithm first deals with small vertex cuts and vertices of degree \({\ge }5\), which may be created in our algorithm even if the input graph has maximum degree 4, then eliminates cycles of length 3 and 4 containing degree-4 vertices, and finally branches on degree-4 vertices. We invoke an exact algorithm for this problem in graphs with maximum degree 3 directly when the graph has no vertices of degree \({\ge }4\). Branching on degree-4 vertices on special local structures will be the bottleneck case, and we carefully design rules of choosing degree-4 vertices to branch on so that the resulting instances after branching decrease the measure effectively in the next step.     

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.     

On L(2,1)-labeling of generalized Petersen graphs

A variation of the classical channel assignment problem is to assign a radio channel which is a nonnegative integer to each radio transmitter so that ??close?? transmitters must receive different channels and ??very close?? transmitters must receive channels that are at least two channels apart. The goal is to minimize the span of a feasible assignment. This channel assignment problem can be modeled with distance-dependent graph labelings. A k-L(2,1)-labeling of a graph G is a mapping f from the vertex set of G to the set {0,1,2,??,k} such that |f(x)?f(y)|??2 if d(x,y)=1 and $f(x)\not =f(y)$ if d(x,y)=2, where d(x,y) is the distance between vertices x and y in G. The minimum k for which G admits an k-L(2,1)-labeling, denoted by ??(G), is called the ??-number of G. Very little is known about ??-numbers of 3-regular graphs. In this paper we focus on an important subclass of 3-regular graphs called generalized Petersen graphs. For an integer n??3, a graph G is called a generalized Petersen graph of order n if and only if G is a 3-regular graph consisting of two disjoint cycles (called inner and outer cycles) of length n, where each vertex of the outer (resp. inner) cycle is adjacent to exactly one vertex of the inner (resp. outer) cycle. In 2002, Georges and Mauro conjectured that ??(G)??7 for all generalized Petersen graphs G of order n??7. Later, Adams, Cass and Troxell proved that Georges and Mauro??s conjecture is true for orders 7 and 8. In this paper it is shown that Georges and Mauro??s conjecture is true for generalized Petersen graphs of orders 9, 10, 11 and 12.     

Sharp bounds for Zagreb indices of maximal outerplanar graphs

For a (molecular) graph, the first Zagreb index M ₁ is equal to the sum of squares of the vertex degrees, and the second Zagreb index M ₂ is equal to the sum of products of degrees of pairs of adjacent vertices. In this paper, we investigate the first and the second Zagreb indices of maximal outerplanar graph. We determine sharp upper and lower bounds for M ₁-, M ₂-values among the n-vertex maximal outerplanar graphs. As well we determine sharp upper and lower bounds of Zagreb indices for n-vertex outerplanar graphs (resp. maximal outerplanar graphs) with perfect matchings.     

Safe sets in graphs: Graph classes and structural parameters

A safe set of a graph \(G=(V,E)\) is a non-empty subset S of V such that for every component A of G[S] and every component B of \(G[V {\setminus } S]\), we have \(|A| \ge |B|\) whenever there exists an edge of G between A and B. In this paper, we show that a minimum safe set can be found in polynomial time for trees. We then further extend the result and present polynomial-time algorithms for graphs of bounded treewidth, and also for interval graphs. We also study the parameterized complexity. We show that the problem is fixed-parameter tractable when parameterized by the solution size. Furthermore, we show that this parameter lies between the tree-depth and the vertex cover number. We then conclude the paper by showing hardness for split graphs and planar graphs.     

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