Powers of the Vertex Cover Ideal of a Chordal Graph

In this article, Cohen–Macaulay chordal graphs and generalized star graphs are studied to show that all powers of the vertex cover ideal of such graphs have linear quotients. Moreover, it is shown that the Alexander dual of the clique complex of any chordal graph is vertex decomposable.     

Site percolation and isoperimetric inequalities for plane graphs

We use isoperimetric inequalities combined with a new technique to prove upper bounds for the site percolation threshold of plane graphs with given minimum degree conditions. In the process we prove tight new isoperimetric bounds for certain classes of hyperbolic graphs. This establishes the vertex isoperimetric constant for all triangular and square hyperbolic lattices, answering a question of Lyons and Peres. We prove that plane graphs of minimum degree at least 7 have site percolation threshold bounded away from 1/2, which was conjectured by Benjamini and Schramm, and make progress on a conjecture of Angel, Benjamini, and Horesh that the critical probability is at most 1/2 for plane triangulations of minimum degree 6. We prove additional bounds for stronger minimum degree conditions, and for graphs without triangular faces.     

Isometric embedding in products of complete graphs

An isometric (i.e., distance-preserving) embedding of a connected graph G into a cartesian product of complete graphs is equivalent to a labelling of each vertex of G by a string of symbols of fixed length such that the distance between two vertices is equal to the Hamming distance between the corresponding strings. Such a labelling could provide an addressing scheme for a communications network, since it enables a message to find a shortest path to its destination using only local information.We show that any two such embeddings of the same graph G are essentially the same, and give a polynomial-time algorithm which will find such an embedding if it exists. In addition we characterize the graphs which are isometrically embeddable in powers of K₃.     

Spherical and Clockwise Spherical Graphs

The main subject of our study are spherical (weakly spherical) graphs, i.e. connected graphs fulfilling the condition that in each interval to each vertex there is exactly one (at least one, respectively) antipodal vertex. Our analysis concerns properties of these graphs especially in connection with convexity and also with hypercube graphs. We deal e.g. with the problem under what conditions all intervals of a spherical graph induce hypercubes and find a new characterization of hypercubes: G is a hypercube if and only if G is spherical and bipartite.     

An Ant Colony Optimization Algorithm for the Minimum Weight Vertex Cover Problem

Given an undirected graph and a weighting function defined on the vertex set, the minimum weight vertex cover problem is to find a vertex subset whose total weight is minimum subject to the premise that the selected vertices cover all edges in the graph. In this paper, we introduce a meta-heuristic based upon the Ant Colony Optimization (ACO) approach, to find approximate solutions to the minimum weight vertex cover problem. In the literature, the ACO approach has been successfully applied to several well-known combinatorial optimization problems whose solutions might be in the form of paths on the associated graphs. A solution to the minimum weight vertex cover problem however needs not to constitute a path. The ACO algorithm proposed in this paper incorporates several new features so as to select vertices out of the vertex set whereas the total weight can be minimized as much as possible. Computational experiments are designed and conducted to study the performance of our proposed approach. Numerical results evince that the ACO algorithm demonstrates significant effectiveness and robustness in solving the minimum weight vertex cover problem.     

On the Spectral Gap of a Quantum Graph

We consider the problem of finding universal bounds of “isoperimetric” or “isodiametric” type on the spectral gap of the Laplacian on a metric graph with natural boundary conditions at the vertices, in terms of various analytical and combinatorial properties of the graph: its total length, diameter, number of vertices and number of edges. We investigate which combinations of parameters are necessary to obtain non-trivial upper and lower bounds and obtain a number of sharp estimates in terms of these parameters. We also show that, in contrast to the Laplacian matrix on a combinatorial graph, no bound depending only on the diameter is possible. As a special case of our results on metric graphs, we deduce estimates for the normalised Laplacian matrix on combinatorial graphs which, surprisingly, are sometimes sharper than the ones obtained by purely combinatorial methods in the graph theoretical literature.     

Minimal split completions

We study the problem of adding an inclusion minimal set of edges to a given arbitrary graph so that the resulting graph is a split graph, called a minimal split completion of the input graph. Minimal completions of arbitrary graphs into chordal and interval graphs have been studied previously, and new results have been added recently. We extend these previous results to split graphs by giving a linear-time algorithm for computing minimal split completions. We also give two characterizations of minimal split completions, which lead to a linear time algorithm for extracting a minimal split completion from any given split completion.We prove new properties of split graph that are both useful for our algorithms and interesting on their own. First, we present a new way of partitioning the vertices of a split graph uniquely into three subsets. Second, we prove that split graphs have the following property: given two split graphs on the same vertex set where one is a subgraph of the other, there is a sequence of edges that can be removed from the larger to obtain the smaller such that after each edge removal the modified graph is split.     

Isoperimetric numbers of graph bundles

The main aim of this paper is to give some upper and lower bounds for the isoperimetric numbers of graph coverings or graph bundles, with exact values in some special cases. In addition, we show that the isoperimetric number of any covering graph is not greater than that of the base graph. Mohar's theorem for the isoperimetric number of the cartesian product of a graph and a complete graph can be extended to a more general case: The isoperimetric numberi(G × K _2n) of the cartesian product of any graphG and a complete graphK _2n on even vertices is the minimum of the isoperimetric numberi(G) andn, and it is also a sharp lower bound of the isoperimetric numbers of all graph bundles over the graphG with fiberK _2n. Furthermore, ifn 2i(G) then the isoperimetric number of any graph bundle overG with fibreK _n is equal to the isoperimetric numberi(G) ofG. Partially supported by The Ministry of Education, Korea.     

Laplacian Spectrum of Weakly Quasi-threshold Graphs

In this paper we study the class of weakly quasi-threshold graphs that are obtained from a vertex by recursively applying the operations (i) adding a new isolated vertex, (ii) adding a new vertex and making it adjacent to all old vertices, (iii) disjoint union of two old graphs, and (iv) adding a new vertex and making it adjacent to all neighbours of an old vertex. This class contains the class of quasi-threshold graphs. We show that weakly quasi-threshold graphs are precisely the comparability graphs of a forest consisting of rooted trees with each vertex of a tree being replaced by an independent set. We also supply a quadratic time algorithm in the the size of the vertex set for recognizing such a graph. We completely determine the Laplacian spectrum of weakly quasi-threshold graphs. It turns out that weakly quasi-threshold graphs are Laplacian integral. As a corollary we obtain a closed formula for the number of spanning trees in such graphs. A conjecture of Grone and Merris asserts that the spectrum of the Laplacian of any graph is majorized by the conjugate of the degree sequence of the graph. We show that the conjecture holds for cographs. Prof. Bapat and Prof. Pati take this opportunity to thank the Indian Institute of Technology Kanpur for the invitation. The authors also wish to thank the Department of Science and Technology, New Delhi for the project grant.     

A solitaire game played on 2-colored graphs

We introduce a solitaire game played on a graph. Initially one disk is placed at each vertex, one face green and the other red, oriented with either color facing up. Each move of the game consists of selecting a vertex whose disk shows green, flipping over the disks at neighboring vertices, and deleting the selected vertex. The game is won if all vertices are eliminated. We derive a simple parity-based necessary condition for winnability of a given game instance. By studying graph operations that construct new graphs from old ones, we obtain broad classes of graphs where this condition also suffices, thus characterizing the winnable games on such graphs. Concerning two familiar (but narrow) classes of graphs, we show that for trees a game is winnable if and only if the number of green vertices is odd, and for n-cubes a game is winnable if and only if the number of green vertices is even and not all vertices have the same color. We provide a linear-time algorithm for deciding winnability for games on maximal outerplanar graphs. We reduce the decision problem for winnability of a game on an arbitrary graph G to winnability of games on its blocks, and to winnability on homeomorphic images of G obtained by contracting edges at 2-valent vertices.     

Stability of cartesian products

We complete the work started by Holton and Grant concerning the semi-stability of non-trivial connected cartesian products and show that all such products are semi-stable. Further we show that except for certain (listed) restricted graphs, connected cartesian products are semi-stable at every vertex. Finally, we show that the cartesian product of any two graphs is not semi-stable if and only if one of them is totally disconnected and the other is not semi-stable.     

Coalescent random walks on graphs

Inspired by coalescent theory in biology, we introduce a stochastic model called “multi-person simple random walks” or “coalescent random walks” on a graph G. There are any finite number of persons distributed randomly at the vertices of G. In each step of this discrete time Markov chain, we randomly pick up a person and move it to a random adjacent vertex. To study this model, we introduce the tensor powers of graphs and the tensor products of Markov processes. Then the coalescent random walk on graph G becomes the simple random walk on a tensor power of G. We give estimates of expected number of steps for these persons to meet all together at a specific vertex. For regular graphs, our estimates are exact.     

Primitivity and independent sets in direct products of vertex‐transitive graphs

We introduce the concept of the primitivity of independent set in vertex‐transitive graphs, and investigate the relationship between the primitivity and the structure of maximum independent sets in direct products of vertex‐transitive graphs. As a consequence of our main results, we positively solve an open problem related to the structure of independent sets in powers of vertex‐transitive graphs. © 2010 Wiley Periodicals, Inc. J Graph Theory 67: 218‐225, 2011     

Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs

We study a variation of the vertex cover problem where it is required that the graph induced by the vertex cover is connected. We prove that this problem is polynomial in chordal graphs, has a PTAS in planar graphs, is APX-hard in bipartite graphs and is 5/3-approximable in any class of graphs where the vertex cover problem is polynomial (in particular in bipartite graphs). Finally, dealing with hypergraphs, we study the complexity and the approximability of two natural generalizations.     

Toric rings arising from vertex cover ideals

We extend the sortability concept to monomial ideals which are not necessarily generated in one degree and as an application we obtain normal Cohen-Macaulay toric rings attached to vertex cover ideals of graphs. Moreover, we consider a construction on a graph called a clique multi-whiskering which always produces vertex cover ideals with componentwise linear powers.     

Combinatorial symbolic powers

Symbolic powers are studied in the combinatorial context of monomial ideals. When the ideals are generated by quadratic squarefree monomials, the generators of the symbolic powers are obstructions to vertex covering in the associated graph and its blowups. As a result, perfect graphs play an important role in the theory, dual to the role played by perfect graphs in the theory of secants of monomial ideals. We use Gröbner degenerations as a tool to reduce questions about symbolic powers of arbitrary ideals to the monomial case. Among the applications are a new, unified approach to the Gröbner bases of symbolic powers of determinantal and Pfaffian ideals.     

A connection between a convex programming problem and the LYM property on perfect graphs

We derive three equivalent conditions on a perfect graph concerning the optimal solution of a convex programming problem, the length-width inequality, and the simultaneous vertex covering by cliques and anticliques. By combining proof techniques including Lagrangian dual, Dilworth's Theorem, and Kuhn-Tucker Theorem, we establish a strong connection between the three topics. This provides new insights into the structure of perfect graphs. The famous Lubell-Yamamoto-Meschalkin (LYM) Property or Sperner Property for partially ordered sets is a specialization of our results to a subclass of perfect graphs.     

A polynomial time algorithm for finding the prime factors of cartesian-product graphs

We consider the computational complexity of recognizinf concerned cartesian product graphs. Sabidussi gives a non-algorithmic proof that the cartesian factorization is unique. He uses a tower of successively coarser equivalence relations on the edge set in which each prime factor of the graph is identified with an equivalence class in the coarsest of the relations. We first explore the structure and size of the relation at the base of the tower. Then we give a polynomial-time algorithm to compute the relations and to construct the prime factors of any connected graph. The bounds on the size of the relations are crucial to the runtime analysis of our algorithm.     

Planar Hypohamiltonian Graphs on 40 Vertices

A graph is hypohamiltonian if it is not Hamiltonian, but the deletion of any single vertex gives a Hamiltonian graph. Until now, the smallest known planar hypohamiltonian graph had 42 vertices, a result due to Araya and Wiener. That result is here improved upon by 25 planar hypohamiltonian graphs of order 40, which are found through computer‐aided generation of certain families of planar graphs with girth 4 and a fixed number of 4‐faces. It is further shown that planar hypohamiltonian graphs exist for all orders greater than or equal to 42. If Hamiltonian cycles are replaced by Hamiltonian paths throughout the definition of hypohamiltonian graphs, we get the definition of hypotraceable graphs. It is shown that there is a planar hypotraceable graph of order 154 and of all orders greater than or equal to 156. We also show that the smallest planar hypohamiltonian graph of girth 5 has 45 vertices.     

Optimal broadcast domination in polynomial time

Broadcast domination was introduced by Erwin in 2002, and it is a variant of the standard dominating set problem, such that different vertices can be assigned different domination powers. Broadcast domination assigns an integer power f(v)?0 to each vertex v of a given graph, such that every vertex of the graph is within distance f(v) from some vertex v having f(v)?1. The optimal broadcast domination problem seeks to minimize the sum of the powers assigned to the vertices of the graph. Since the presentation of this problem its computational complexity has been open, and the general belief has been that it might be NP-hard. In this paper, we show that optimal broadcast domination is actually in P, and we give a polynomial time algorithm for solving the problem on arbitrary graphs, using a non-standard approach.