Improved induced matchings in sparse graphs

An induced matching in a graph G=(V,E) is a matching M such that (V,M) is an induced subgraph of G. Clearly, among two vertices with the same neighbourhood (called twins) at most one is matched in any induced matching, and if one of them is matched then there is another matching of the same size that matches the other vertex. Motivated by this, Kanj et al. [10] studied induced matchings in twinless graphs. They showed that any twinless planar graph contains an induced matching of size at least and that there are twinless planar graphs that do not contain an induced matching of size greater than . We improve both these bounds to , which is tight up to an additive constant. This implies that the problem of deciding whether a planar graph has an induced matching of size k has a kernel of size at most 28k. We also show for the first time that this problem is fixed parameter tractable for graphs of bounded arboricity.Kanj et al. also presented an algorithm which decides in -time whether an n-vertex planar graph contains an induced matching of size k. Our results improve the time complexity analysis of their algorithm. However, we also show a more efficient -time algorithm. Its main ingredient is a new, O^∗(4^l)-time algorithm for finding a maximum induced matching in a graph of branch width at most l.     

The Laplacian spectral radius of some bipartite graphs

In this paper, we study the largest Laplacian spectral radius of the bipartite graphs with n vertices and k cut edges and the bicyclic bipartite graphs, respectively. Identifying the center of a star K_1,k and one vertex of degree n of K_m,n, we denote by the resulting graph. We show that the graph (1?k?n-4) is the unique graph with the largest Laplacian spectral radius among the bipartite graphs with n vertices and k cut edges, and (n?7) is the unique graph with the largest Laplacian spectral radius among all the bicyclic bipartite graphs.     

On maximizing clique, clique-Helly and hereditary clique-Helly induced subgraphs

Clique-Helly and hereditary clique-Helly graphs are polynomial-time recognizable. Recently, we presented a proof that the clique graph recognition problem is NP-complete [L. Alcón, L. Faria, C.M.H. de Figueiredo, M. Gutierrez, Clique graph recognition is NP-complete, in: Proc. WG 2006, in: Lecture Notes in Comput. Sci., vol. 4271, Springer, 2006, pp. 269-277]. In this work, we consider the decision problems: given a graph G=(V,E) and an integer k≥0, we ask whether there exists a subset V^′⊆V with |V^′|≥k such that the induced subgraph G[V^′] of G is, variously, a clique, clique-Helly or hereditary clique-Helly graph. The first problem is clearly NP-complete, from the above reference; we prove that the other two decision problems mentioned are NP-complete, even for maximum degree 6 planar graphs. We consider the corresponding maximization problems of finding a maximum induced subgraph that is, respectively, clique, clique-Helly or hereditary clique-Helly. We show that these problems are Max SNP-hard, even for maximum degree 6 graphs. We show a general polynomial-time -approximation algorithm for these problems when restricted to graphs with fixed maximum degree Δ. We generalize these results to other graph classes. We exhibit a polynomial 6-approximation algorithm to minimize the number of vertices to be removed in order to obtain a hereditary clique-Helly subgraph.     

Colouring lines in projective space

Let V be a vector space of dimension v over a field of order q. The q-Kneser graph has the k-dimensional subspaces of V as its vertices, where two subspaces α and β are adjacent if and only if is the zero subspace. This paper is motivated by the problem of determining the chromatic numbers of these graphs. This problem is trivial when k=1 (and the graphs are complete) or when v<2k (and the graphs are empty). We establish some basic theory in the general case. Then specializing to the case k=2, we show that the chromatic number is q²+q when v=4 and (q^v-1-1)/(q-1) when v>4. In both cases we characterise the minimal colourings.     

On colorings of graph powers

In this paper, some results concerning the colorings of graph powers are presented. The notion of helical graphs is introduced. We show that such graphs are hom-universal with respect to high odd-girth graphs whose (2t+1)th power is bounded by a Kneser graph according to the homomorphism order. Also, we consider the problem of existence of homomorphism to odd cycles. We prove that such homomorphism to a (2k+1)-cycle exists if and only if the chromatic number of the (2k+1)th power of is less than or equal to 3, where is the 3-subdivision of G. We also consider Nešet?il’s Pentagon problem. This problem is about the existence of high girth cubic graphs which are not homomorphic to the cycle of size five. Several problems which are closely related to Nešet?il’s problem are introduced and their relations are presented.     

Rainbow domination on trees

This paper studies a variation of domination in graphs called rainbow domination. For a positive integer k, a k-rainbow dominating function of a graph G is a function f from V(G) to the set of all subsets of {1,2,…,k} such that for any vertex v with f(v)=0? we have ∪_u∈NG(v)f(u)={1,2,…,k}. The 1-rainbow domination is the same as the ordinary domination. The k-rainbow domination problem is to determine the k-rainbow domination number of a graph G, that is the minimum value of ∑_v∈V(G)|f(v)| where f runs over all k-rainbow dominating functions of G. In this paper, we prove that the k-rainbow domination problem is NP-complete even when restricted to chordal graphs or bipartite graphs. We then give a linear-time algorithm for the k-rainbow domination problem on trees. For a given tree T, we also determine the smallest k such that .     

The cubicity of hypercube graphs

For a graph G, its cubicity is the minimum dimension k such that G is representable as the intersection graph of (axis-parallel) cubes in k-dimensional space. (A k-dimensional cube is a Cartesian product R₁×R₂×?×R_k, where R_i is a closed interval of the form [a_i,a_i+1] on the real line.) Chandran et al. [L.S. Chandran, C. Mannino, G. Oriolo, On the cubicity of certain graphs, Information Processing Letters 94 (2005) 113-118] showed that for a d-dimensional hypercube H_d, . In this paper, we use the probabilistic method to show that . The parameter boxicity generalizes cubicity: the boxicity of a graph G is defined as the minimum dimension k such that G is representable as the intersection graph of axis-parallel boxes in k-dimensional space. Since for any graph G, our result implies that . The problem of determining a non-trivial lower bound for is left open.     

Cube intersection concepts in median graphs

In this paper, we study different classes of intersection graphs of maximal hypercubes of median graphs. For a median graph G and k≥0, the intersection graph Q_k(G) is defined as the graph whose vertices are maximal hypercubes (by inclusion) in G, and two vertices H_x and H_y in Q_k(G) are adjacent whenever the intersection H_x∩H_y contains a subgraph isomorphic to Q_k. Characterizations of clique-graphs in terms of these intersection concepts when k>0, are presented. Furthermore, we introduce the so-called maximal 2-intersection graph of maximal hypercubes of a median graph G, denoted , whose vertices are maximal hypercubes of G, and two vertices are adjacent if the intersection of the corresponding hypercubes is not a proper subcube of some intersection of two maximal hypercubes. We show that a graph H is diamond-free if and only if there exists a median graph G such that H is isomorphic to . We also study convergence of median graphs to the one-vertex graph with respect to all these operations.     

Partial characterizations of clique-perfect graphs II: Diamond-free and Helly circular-arc graphs

A clique-transversal of a graph G is a subset of vertices that meets all the cliques of G. A clique-independent set is a collection of pairwise vertex-disjoint cliques. A graph G is clique-perfect if the sizes of a minimum clique-transversal and a maximum clique-independent set are equal for every induced subgraph of G. The list of minimal forbidden induced subgraphs for the class of clique-perfect graphs is not known. Another open question concerning clique-perfect graphs is the complexity of the recognition problem. Recently we were able to characterize clique-perfect graphs by a restricted list of forbidden induced subgraphs when the graph belongs to two different subclasses of claw-free graphs. These characterizations lead to polynomial time recognition of clique-perfect graphs in these classes of graphs. In this paper we solve the characterization problem in two new classes of graphs: diamond-free and Helly circular-arc () graphs. This last characterization leads to a polynomial time recognition algorithm for clique-perfect graphs.     

Asymmetric marking games on line graphs

This paper investigates the asymmetric marking games on line graphs. Suppose G is a graph with maximum degree Δ and G has an orientation with maximum outdegree k, we show that the (a,1)-game coloring number of the line graph of G is at most . When a=1, this improves some known results of the game coloring number of the line graphs.     

Improved bottleneck domination algorithms

W.C.K. Yen introduced BOTTLENECK DOMINATION and BOTTLENECK INDEPENDENT DOMINATION. He presented an -time algorithm to compute a minimum bottleneck dominating set. He also obtained that the BOTTLENECK INDEPENDENT DOMINATING SET problem is NP-complete, even when restricted to planar graphs.We present simple linear time algorithms for the BOTTLENECK DOMINATING SET and the BOTTLENECK TOTAL DOMINATING SET problem. Furthermore, we give polynomial time algorithms (most of them with linear time-complexities) for the BOTTLENECK INDEPENDENT DOMINATING SET problem on the following graph classes: AT-free graphs, chordal graphs, split graphs, permutation graphs, graphs of bounded treewidth, and graphs of clique-width at most k with a given k-expression.     

Cubicity, boxicity, and vertex cover

A k-dimensional box is the cartesian product R₁×R₂×?×R_k where each R_i is a closed interval on the real line. The boxicity of a graph G, denoted as box(G), is the minimum integer k such that G is the intersection graph of a collection of k-dimensional boxes. A unit cube in k-dimensional space or a k-cube is defined as the cartesian product R₁×R₂×?×R_k where each R_i is a closed interval on the real line of the form [a_i,a_i+1]. The cubicity of G, denoted as cub(G), is the minimum k such that G is the intersection graph of a collection of k-cubes. In this paper we show that cub(G)≤t+⌈log(n−t)⌉−1 and , where t is the cardinality of a minimum vertex cover of G and n is the number of vertices of G. We also show the tightness of these upper bounds.F.S. Roberts in his pioneering paper on boxicity and cubicity had shown that for a graph G, and , where n is the number of vertices of G, and these bounds are tight. We show that if G is a bipartite graph then and this bound is tight. We also show that if G is a bipartite graph then . We point out that there exist graphs of very high boxicity but with very low chromatic number. For example there exist bipartite (i.e., 2 colorable) graphs with boxicity equal to . Interestingly, if boxicity is very close to , then chromatic number also has to be very high. In particular, we show that if , s≥0, then , where χ(G) is the chromatic number of G.     

2-resonance of plane bipartite graphs and its applications to boron-nitrogen fullerenes

A set H of disjoint faces of a plane bipartite graph G is a resonant pattern if G has a perfect matching M such that the boundary of each face in H is an M-alternating cycle. An elementary result was obtained [Discrete Appl. Math. 105 (2000) 291-311]: a plane bipartite graph is 1-extendable if and only if every face forms a resonant pattern. In this paper we show that for a 2-extendable plane bipartite graph, any pair of disjoint faces form a resonant pattern, and the converse does not necessarily hold. As an application, we show that all boron-nitrogen (B-N) fullerene graphs are 2-resonant, and construct all the 3-resonant B-N fullerene graphs, which are all k-resonant for any positive integer k. Here a B-N fullerene graph is a plane cubic graph with only square and hexagonal faces, and a B-N fullerene graph is k-resonant if any disjoint faces form a resonant pattern. Finally, the cell polynomials of 3-resonant B-N fullerene graphs are computed.     

Complexity results in graph reconstruction

We investigate the relative complexity of the graph isomorphism problem (GI) and problems related to the reconstruction of a graph from its vertex-deleted or edge-deleted subgraphs (in particular, deck checking (DC) and legitimate deck (LD) problems). We show that these problems are closely related for all amounts c?1 of deletion:

(1)

, , , and .

(2)

For all k?2, and .

(3)

For all k?2, .

(4)

.

(5)

For all k?2, .

For many of these results, even the c=1 case was not previously known.Similar to the definition of reconstruction numbers vrn_∃(G) [F. Harary, M. Plantholt, The graph reconstruction number, J. Graph Theory 9 (1985) 451-454] and ern_∃(G) (see [J. Lauri, R. Scapellato Topics in Graph Automorphism and Reconstruction, London Mathematical Society, Cambridge University Press, Cambridge, 2003, p. 120]), we introduce two new graph parameters, vrn_∀(G) and ern_∀(G), and give an example of a family {G_n}_n?4 of graphs on n vertices for which vrn_∃(G_n)<vrn_∀(G_n). For every k?2 and n?1, we show that there exists a collection of k graphs on (2^k-1+1)n+k vertices with 2ⁿ 1-vertex-preimages, i.e., one has families of graph collections whose number of 1-vertex-preimages is huge relative to the size of the graphs involved.     

Algorithms for clique-independent sets on subclasses of circular-arc graphs

A circular-arc graph is the intersection graph of arcs on a circle. A Helly circular-arc graph is a circular-arc graph admitting a model whose arcs satisfy the Helly property. A clique-independent set of a graph is a set of pairwise disjoint cliques of the graph. It is NP-hard to compute the maximum cardinality of a clique-independent set for a general graph. In the present paper, we propose polynomial time algorithms for finding the maximum cardinality and weight of a clique-independent set of a -free CA graph. Also, we apply the algorithms to the special case of an HCA graph. The complexity of the proposed algorithm for the cardinality problem in HCA graphs is O(n). This represents an improvement over the existing algorithm by Guruswami and Pandu Rangan, whose complexity is O(n²). These algorithms suppose that an HCA model of the graph is given.     

Color-critical graphs have logarithmic circumference

A graph G is k-critical if every proper subgraph of G is (k−1)-colorable, but the graph G itself is not. We prove that every k-critical graph on n vertices has a cycle of length at least , improving a bound of Alon, Krivelevich and Seymour from 2000. Examples of Gallai from 1963 show that the bound cannot be improved to exceed . We thus settle the problem of bounding the minimal circumference of k-critical graphs, raised by Dirac in 1952 and Kelly and Kelly in 1954.     

Remarks on the minus (signed) total domination in graphs

A function f:V(G)→{+1,0,-1} defined on the vertices of a graph G is a minus total dominating function if the sum of its function values over any open neighborhood is at least 1. The minus total domination number of G is the minimum weight of a minus total dominating function on G. By simply changing “{+1,0,-1}” in the above definition to “{+1,-1}”, we can define the signed total dominating function and the signed total domination number of G. In this paper we present a sharp lower bound on the signed total domination number for a k-partite graph, which results in a short proof of a result due to Kang et al. on the minus total domination number for a k-partite graph. We also give sharp lower bounds on and for triangle-free graphs and characterize the extremal graphs achieving these bounds.     

Variations of Y-dominating functions on graphs

Let Y be a subset of real numbers. A Y-dominating function of a graph G=(V,E) is a function f:V→Y such that for all vertices v∈V, where N_G[v]={v}∪{u|(u,v)∈E}. Let for any subset S of V and let f(V) be the weight of f. The Y-domination problem is to find a Y-dominating function of minimum weight for a graph G=(V,E). In this paper, we study the variations of Y-domination such as {k}-domination, k-tuple domination, signed domination, and minus domination for some classes of graphs. We give formulas to compute the {k}-domination, k-tuple domination, signed domination, and minus domination numbers of paths, cycles, n-fans, n-wheels, n-pans, and n-suns. Besides, we present a unified approach to these four problems on strongly chordal graphs. Notice that trees, block graphs, interval graphs, and directed path graphs are subclasses of strongly chordal graphs. This paper also gives complexity results for the problems on doubly chordal graphs, dually chordal graphs, bipartite planar graphs, chordal bipartite graphs, and planar graphs.