 |
Discrete Mathematics & Theoretical Computer Science |
Graph and Algorithms
On-line ranking of split graphs
A vertex ranking of a graph G is an assignment of positive integers (colors) to the vertices of G such that each path connecting two vertices of the same color contains a vertex of a higher color. Our main goal is to find a vertex ranking using as few colors as possible. Considering on-line algorithms for vertex ranking of split graphs, we prove that the worst case ratio of the number of colors used by any on-line ranking algorithm and the number of colors used in an optimal off-line solution may be arbitrarily large. This negative result motivates us to investigate semi on-line algorithms, where a split graph is presented on-line but its clique number is given in advance. We prove that there does not exist a (2-ɛ)-competitive semi on-line algorithm of this type. Finally, a 2-competitive semi on-line algorithm is given.
List edge and list total colorings of planar graphs without non-induced 7-cycles
Giving a planar graph G, let χ'l(G) and χ''l(G) denote the list edge chromatic number and list total chromatic number of G respectively. It is proved that if G is a planar graph without non-induced 7-cycles, then χ'l(G)≤Δ(G)+1 and χ''l(G)≤Δ(G)+2 where Δ(G)≥7.
Hereditary biclique-Helly graphs: recognition and maximal biclique enumeration
A biclique is a set of vertices that induce a complete bipartite graph. A graph G is biclique-Helly when its family of maximal bicliques satisfies the Helly property. If every induced subgraph of G is also biclique-Helly, then G is hereditary biclique-Helly. A graph is C4-dominated when every cycle of length 4 contains a vertex that is dominated by the vertex of the cycle that is not adjacent to it. In this paper we show that the class of hereditary biclique-Helly graphs is formed precisely by those C4-dominated graphs that contain no triangles and no induced cycles of length either 5 or 6. Using this characterization, we develop an algorithm for recognizing hereditary biclique-Helly graphs in O(n2+αm) time and O(n+m) space. (Here n, m, and α= O(m1/2) are the number of vertices and edges, and the arboricity of the graph, respectively.) As a subprocedure, we show how to recognize those C4-dominated graphs that contain no triangles in O(αm) time and O(n+m) space. Finally, we show how to enumerate all the maximal bicliques of a C4-dominated graph with no triangles in O(n2 + αm) time and O(αm) space.
Some results on stable sets for k-colorable P₆-free graphs and generalizations
This article deals with the Maximum Weight Stable Set (MWS) problem (and some other related NP-hard problems) and the class of P-6-free graphs. The complexity status of MWS is open for P-6-free graphs and is open even for P-5-free graphs (as a long standing open problem). Several results are known for MWS on subclasses of P-5-free: in particular, MWS can be solved for k-colorable P-5-free graphs in polynomial time for every k (depending on k) and more generally for (P-5, K-p)-free graphs (depending on p), which is a useful result since for every graph G one can easily compute a k-coloring of G, with k not necessarily minimum. This article studies the MWS problem for k-colorable P-6-free graphs and more generally for (P-6, K-p)-free graphs. Though we were not able to define a polynomial time algorithm for this problem for every k, this article introduces: (i) some structure properties of P-6-free graphs with respect to stable sets, (ii) two reductions for MWS on (P-6; K-p)-free graphs for every p, (iii) three polynomial time algorithms to solve MWS respectively for 3-colorable P-6-free, for 4-colorable P-6-free, and for (P-6, K-4)-free graphs (the latter allows one to state, together with other known results, that MWS can be solved for (P-6, F)-free graphs in polynomial time where F is any four vertex graph).
On neighbour-distinguishing colourings from lists
An edge colouring of a graph is said to be neighbour-distinguishing if any two adjacent vertices have distinct sets of colours of their incident edges. In this paper the list version of the problem of determining the minimum number of colours in a neighbour-distinguishing colouring of a given graph is considered.
Bounds for the minimum oriented diameter
We consider the problem of determining an orientation with minimum diameter MOD(G) of a connected and bridge-less graph G. In 2001 Fomin et al. discovered the relation MOD(G) <= 9 gamma(G) - 5 between the minimum oriented diameter and the size gamma(G) of a minimum dominating set. We improve their upper bound to MOD(G) <= 4 gamma(G).
A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set
An independent dominating set D of a graph G = (V,E) is a subset of vertices such that every vertex in V \ D has at least one neighbor in D and D is an independent set, i.e. no two vertices of D are adjacent in G. Finding a minimum independent dominating set in a graph is an NP-hard problem. Whereas it is hard to cope with this problem using parameterized and approximation algorithms, there is a simple exact O(1.4423^n)-time algorithm solving the problem by enumerating all maximal independent sets. In this paper we improve the latter result, providing the first non trivial algorithm computing a minimum independent dominating set of a graph in time O(1.3569^n). Furthermore, we give a lower bound of \Omega(1.3247^n) on the worst-case running time of this algorithm, showing that the running time analysis is almost tight.
On hamiltonian chain saturated uniform hypergraphs
We say that a hypergraph H is hamiltonian chain saturated if H does not contain a hamiltonian chain but by adding any new edge we create a hamiltonian chain in H. In this paper we ask about the smallest size of a k-uniform hamiltonian chain saturated hypergraph. We present a construction of a family of k-uniform hamiltonian chain saturated hypergraphs with O(n(k-1/2)) edges.
Vertex-colouring edge-weightings with two edge weights
An edge-weighting vertex colouring of a graph is an edge-weight assignment such that the accumulated weights at the vertices yields a proper vertex colouring. If such an assignment from a set S exists, we say the graph is S-weight colourable. It is conjectured that every graph with no isolated edge is \1, 2, 3\-weight colourable. We explore the problem of classifying those graphs which are \1, 2\ -weight colourable. We establish that a number of classes of graphs are S -weight colourable for much more general sets S of size 2. In particular, we show that any graph having only cycles of length 0 mod 4 is S -weight colourable for most sets S of size 2. As a consequence, we classify the minimal graphs which are not \1, 2\-weight colourable with respect to subgraph containment. We also demonstrate techniques for constructing graphs which are not \1, 2\-weight colourable.
8-star-choosability of a graph with maximum average degree less than 3
A proper vertex coloring of a graphGis called a star-coloring if there is no path on four vertices assigned to two colors. The graph G is L-star-colorable if for a given list assignment L there is a star-coloring c such that c(v) epsilon L(v). If G is L-star-colorable for any list assignment L with vertical bar L(v)vertical bar \textgreater= k for all v epsilon V(G), then G is called k-star-choosable. The star list chromatic number of G, denoted by X-s(l)(G), is the smallest integer k such that G is k-star-choosable. In this article, we prove that every graph G with maximum average degree less than 3 is 8-star-choosable. This extends a result that planar graphs of girth at least 6 are 8-star-choosable [A. Kundgen, C. Timmons, Star coloring planar graphs from small lists, J. Graph Theory, 63(4): 324-337, 2010].
On packing of two copies of a hypergraph
A 2-packing of a hypergraph H is a permutation sigma on V (H) such that if an edge e belongs to epsilon(H), then sigma(e) does not belong to epsilon(H). Let H be a hypergraph of order n which contains edges of cardinality at least 2 and at most n - 2. We prove that if H has at most n - 2 edges then it is 2-packable.
On the complexity of vertex-coloring edge-weightings
Given a graph G = (V; E) and a weight function omega : E -\textgreater R, a coloring of vertices of G, induced by omega, is defined by chi(omega) (nu) = Sigma(e(sic)nu) omega (e) for all nu is an element of V. In this paper, we show that determining whether a particular graph has a weighting of the edges from \1, 2\ that induces a proper vertex coloring is NP-complete.
On the Book Thickness of k-Trees
Every k-tree has book thickness at most k + 1, and this bound is best possible for all k \textgreater= 3. Vandenbussche et al. [SIAM J. Discrete Math., 2009] proved that every k-tree that has a smooth degree-3 tree decomposition with width k has book thickness at most k. We prove this result is best possible for k \textgreater= 4, by constructing a k-tree with book thickness k + 1 that has a smooth degree-4 tree decomposition with width k. This solves an open problem of Vandenbussche et al.
Colouring the Square of the Cartesian Product of Trees
We prove upper and lower bounds on the chromatic number of the square of the cartesian product of trees. The bounds are equal if each tree has even maximum degree.
Avoidance colourings for small nonclassical Ramsey numbers
The irredundant Ramsey number s - s(m, n) [upper domination Ramsey number u - u(m, n), respectively] is the smallest natural number s [u, respectively] such that in any red-blue edge colouring (R, B) of the complete graph of order s [u, respectively], it holds that IR(B) \textgreater= m or IR(R) \textgreater= n [Gamma (B) \textgreater= m or Gamma(R) \textgreater= n, respectively], where Gamma and IR denote respectively the upper domination number and the irredundance number of a graph. Furthermore, the mixed irredundant Ramsey number t = t(m, n) [mixed domination Ramsey number v = v(m, n), respectively] is the smallest natural number t [v, respectively] such that in any red-blue edge colouring (R, B) of the complete graph of order t [v, respectively], it holds that IR(B) \textgreater= m or beta(R) \textgreater= n [Gamma(B) \textgreater= m or beta(R) \textgreater= n, respectively], where beta denotes the independent domination number of a graph. These four classes of non-classical Ramsey numbers have previously been studied in the literature. In this paper we introduce a new Ramsey number w = w(m, n), called the irredundant-domination Ramsey number, which is the smallest natural number w such that in any red-blue edge colouring (R, B) of the complete graph of order w, it holds that IR(B) \textgreater= m or Gamma(R) \textgreater= n. A computer search is employed to determine complete sets of avoidance colourings of small order for these five classes of nonclassical Ramsey […]
Random 2-SAT Solution Components and a Fitness Landscape
We describe a limiting distribution for the number of connected components in the subgraph of the discrete cube induced by the satisfying assignments to a random 2-SAT formula. We show that, for the probability range where formulas are likely to be satisfied, the random number of components converges weakly (in the number of variables) to a distribution determined by a Poisson random variable. The number of satisfying assignments or solutions is known to grow exponentially in the number of variables. Thus, our result implies that exponentially many solutions are organized into a stochastically bounded number of components. We also describe an application to biological evolution; in particular, to a type of fitness landscape where satisfying assignments represent viable genotypes and connectivity of genotypes is limited by single site mutations. The biological result is that, with probability approaching 1, each viable genotype is connected by single site mutations to an exponential number of other viable genotypes while the number of viable clusters is finite.
Parameterized Problems Related to Seidel's Switching
Seidel's switching is a graph operation which makes a given vertex adjacent to precisely those vertices to which it was non-adjacent before, while keeping the rest of the graph unchanged. Two graphs are called switching-equivalent if one can be made isomorphic to the other by a sequence of switches. In this paper, we continue the study of computational complexity aspects of Seidel's switching, concentrating on Fixed Parameter Complexity. Among other results we show that switching to a graph with at most k edges, to a graph of maximum degree at most k, to a k-regular graph, or to a graph with minimum degree at least k are fixed parameter tractable problems, where k is the parameter. On the other hand, switching to a graph that contains a given fixed graph as an induced subgraph is W [1]-complete. We also show the NP-completeness of switching to a graph with a clique of linear size, and of switching to a graph with small number of edges. A consequence of the latter result is the NP-completeness of Maximum Likelihood Decoding of graph theoretic codes based on complete graphs.
An expected polynomial time algorithm for coloring 2-colorable 3-graphs
We present an algorithm that for 2-colorable 3-uniform hypergraphs, finds a 2-coloring in average running time O (n(5) log(2) n).
Cycle transversals in bounded degree graphs
In this work we investigate the algorithmic complexity of computing a minimum C(k)-transversal, i.e., a subset of vertices that intersects all the chordless cycles with k vertices of the input graph, for a fixed k \textgreater= 3. For graphs of maximum degree at most three, we prove that this problem is polynomial-time solvable when k \textless= 4, and NP-hard otherwise. For graphs of maximum degree at most four, we prove that this problem is NP-hard for any fixed k \textgreater= 3. We also discuss polynomial-time approximation algorithms for computing C(3)-transversals in graphs of maximum degree at most four, based on a new decomposition theorem for such graphs that leads to useful reduction rules.
Tree-width and large grid minors in planar graphs
We show that for a planar graph with no g-grid minor there exists a tree-decomposition of width at most 5g - 6. The proof is constructive and simple. The underlying algorithm for the tree-decomposition runs in O(n(2) log n) time.
Irregular edge coloring of 2-regular graphs
Let G be a simple graph and let us color its edges so that the multisets of colors around each vertex are distinct. The smallest number of colors for which such a coloring exists is called the irregular coloring number of G and is denoted by c(G). We determine the exact value of the irregular coloring number for almost all 2-regular graphs. The results obtained provide new examples demonstrating that a conjecture by Burris is false. As another consequence, we also determine the value of a graph invariant called the point distinguishing index (where sets, instead of multisets, are required to be distinct) for the same family of graphs.
Binary Labelings for Plane Quadrangulations and their Relatives
Motivated by the bijection between Schnyder labelings of a plane triangulation and partitions of its inner edges into three trees, we look for binary labelings for quadrangulations (whose edges can be partitioned into two trees). Our labeling resembles many of the properties of Schnyder's one for triangulations: Apart from being in bijection with tree decompositions, paths in these trees allow to define the regions of a vertex such that counting faces in them yields an algorithm for embedding the quadrangulation, in this case on a 2-book. Furthermore, as Schnyder labelings have been extended to 3-connected plane graphs, we are able to extend our labeling from quadrangulations to a larger class of 2-connected bipartite graphs.
Edge-Removal and Non-Crossing Configurations in Geometric Graphs
A geometric graph is a graph G = (V, E) drawn in the plane, such that V is a point set in general position and E is a set of straight-line segments whose endpoints belong to V. We study the following extremal problem for geometric graphs: How many arbitrary edges can be removed from a complete geometric graph with n vertices such that the remaining graph still contains a certain non-crossing subgraph. The non-crossing subgraphs that we consider are perfect matchings, subtrees of a given size, and triangulations. In each case, we obtain tight bounds on the maximum number of removable edges.
Convex Partitions of Graphs induced by Paths of Order Three
A set C of vertices of a graph G is P(3)-convex if v is an element of C for every path uvw in G with u, w is an element of C. We prove that it is NP-complete to decide for a given graph G and a given integer p whether the vertex set of G can be partitioned into p non-empty disjoint P(3)-convex sets. Furthermore, we study such partitions for a variety of graph classes.
Covering codes in Sierpinski graphs
For a graph G and integers a and b, an (a, b)-code of G is a set C of vertices such that any vertex from C has exactly a neighbors in C and any vertex not in C has exactly b neighbors in C. In this paper we classify integers a and b for which there exist (a, b)-codes in Sierpinski graphs.
On a 1, 2 Conjecture
Let us assign positive integers to the edges and vertices of a simple graph G. As a result we obtain a vertex-colouring of G with integers, where a vertex colour is simply a sum of the weight assigned to the vertex itself and the weights of its incident edges. Can we obtain a proper colouring using only weights 1 and 2 for an arbitrary G? We give a positive answer when G is a 3-colourable, complete or 4-regular graph. We also show that it is enough to C use weights from 1 to 11, as well as from 1 to 11 [chi(G)/2] + 1, for an arbitrary graph G.
Linear Time Recognition Algorithms and Structure Theorems for Bipartite Tolerance Graphs and Bipartite Probe Interval Graphs
A graph is a probe interval graph if its vertices can be partitioned into probes and nonprobes with an interval associated to each vertex so that vertices are adjacent if and only if their corresponding intervals intersect and at least one of them is a probe. A graph G = (V, E) is a tolerance graph if each vertex v is an element of V can be associated to an interval I(v) of the real line and a positive real number t(v) such that uv is an element of E if and only if vertical bar I(u) boolean AND I(v)vertical bar >= min \t(u), t(v)\. In this paper we present O(vertical bar V vertical bar + vertical bar E vertical bar) recognition algorithms for both bipartite probe interval graphs and bipartite tolerance graphs. We also give a new structural characterization for each class which follows from the algorithms.
Coloring Geographical Threshold Graphs
We propose a coloring algorithm for sparse random graphs generated by the geographical threshold graph (GTG) model, a generalization of random geometric graphs (RGG). In a GTG, nodes are distributed in a Euclidean space, and edges are assigned according to a threshold function involving the distance between nodes as well as randomly chosen node weights. The motivation for analyzing this model is that many real networks (e. g., wireless networks, the Internet, etc.) need to be studied by using a ''richer'' stochastic model (which in this case includes both a distance between nodes and weights on the nodes). Here, we analyze the GTG coloring algorithm together with the graph's clique number, showing formally that in spite of the differences in structure between GTG and RGG, the asymptotic behavior of the chromatic number is identical: chi = ln n/ln ln n(1 +o(1)). Finally, we consider the leading corrections to this expression, again using the coloring algorithm and clique number to provide bounds on the chromatic number. We show that the gap between the lower and upper bound is within C ln n/(ln ln n)(2), and specify the constant C.
Some properties of semiregular cages
A graph with degree set \r, r + 1\ is said to be semiregular. A semiregular cage is a semiregular graph with given girth g and the least possible order. First, an upper bound on the diameter of semiregular graphs with girth g and order close enough to the minimum possible value is given in this work. As a consequence, these graphs are proved to be maximally connected when the girth g >= 7 is odd. Moreover an upper bound for the order of semiregular cages is given and, as an application, every semiregular cage with degree set \r, r + 1\ is proved to be maximally connected for g is an element of \6, 8\, and when g = 12 for r >= 7 and r not equal 20. Finally it is also shown that every (\r, r + 1\; g)-cage is 3-connected.
Lower Bounds on the Area Requirements of Series-Parallel Graphs
We show that there exist series-parallel graphs requiring Omega(n2(root log n)) area in any straight-line or poly-line grid drawing. Such a result is achieved in two steps. First, we show that, in any straight-line or poly-line drawing of K(2,n), one side of the bounding box has length Omega(n), thus answering two questions posed by Biedl et al. Second, we show a family of series-parallel graphs requiring Omega(2(root log n)) width and Omega(2(root log n)) height in any straight-line or poly-line grid drawing. Combining the two results, the Omega(n2(root log n)) area lower bound is achieved.
Acyclic colourings of graphs with bounded degree
A k-colouring of a graph G is called acyclic if for every two distinct colours i and j, the subgraph induced in G by all the edges linking a vertex coloured with i and a vertex coloured with j is acyclic. In other words, there are no bichromatic alternating cycles. In 1999 Boiron et al. conjectured that a graph G with maximum degree at most 3 has an acyclic 2-colouring such that the set of vertices in each colour induces a subgraph with maximum degree at most 2. In this paper we prove this conjecture and show that such a colouring of a cubic graph can be determined in polynomial time. We also prove that it is an NP-complete problem to decide if a graph with maximum degree 4 has the above mentioned colouring.
Split-critical and uniquely split-colorable graphs
The split-coloring problem is a generalized vertex coloring problem where we partition the vertices into a minimum number of split graphs. In this paper, we study some notions which are extensively studied for the usual vertex coloring and the cocoloring problem from the point of view of split-coloring, such as criticality and the uniqueness of the minimum split-coloring. We discuss some properties of split-critical and uniquely split-colorable graphs. We describe constructions of such graphs with some additional properties. We also study the effect of the addition and the removal of some edge sets on the value of the split-chromatic number. All these results are compared with their cochromatic counterparts. We conclude with several research directions on the topic.
Spectral characterizations of sun graphs and broken sun graphs
Several matrices can be associated to a graph such as the adjacency matrix or the Laplacian matrix. The spectrum of these matrices gives some informations about the structure of the graph and the question ''Which graphs are determined by their spectrum?'' remains a difficult problem in algebraic graph theory. In this article we enlarge the known families of graphs determined by their spectrum by considering some unicyclic graphs. An odd (resp. even) sun is a graph obtained by appending a pendant vertex to each vertex of an odd (resp. even) cycle. A broken sun is a graph obtained by deleting pendant vertices of a sun. In this paper we prove that a sun is determined by its Laplacian spectrum, an odd sun is determined by its adjacency spectrum (counter-examples are given for even suns) and we give some spectral characterizations of broken suns.
On economical set representations of graphs
In this paper we discuss the bounds of and relations among various kinds of intersection numbers of graphs. Especially, we address extremal graphs with respect to the established bounds. The uniqueness of the minimum-size intersection representations for some graphs is also studied. In the course of this work, we introduce a superclass of chordal graphs, defined in terms of a generalization of simplicial vertex and perfect elimination ordering.
Edge condition for long cycles in bipartite graphs
The following problem was solved by Woodall in 1972: for any pair of nonnegative integers n and k < n/2 - 1 find the minimum integer g(n, k) such that every graph with n vertices and at least g(n, k) edges contains a cycle of length n - k. Woodall proved even more: the size g(n, k), in fact, guarantees the existence of cycles C, for all 3 <= p <= n - k.
In the paper an analogous problem for bipartite graphs is considered. It is proved that every bipartite graph with color classes of cardinalities m and n, m <= n, and size greater than n(m - k - 1) + k + 1 contains a cycle of length 2m - 2k, where m >= 1/2k(2) + 3/2k + 4, k is an element of N. The bound on the number of edges is best possible. Moreover, this size condition guarantees the existence of cycles of all even lengths up to 2m - 2k. We also characterize all extremal graphs for this problem. Finally, we conjecture that the condition on the order may be relaxed to m >= 2k + 2.
Clique-transversal sets and weak 2-colorings in graphs of small maximum degree
A clique-transversal set in a graph is a subset of the vertices that meets all maximal complete subgraphs on at least two vertices. We prove that every connected graph of order n and maximum degree three has a clique-transversal set of size left perpendicular19n/30 + 2/15right perpendicular. This bound is tight, since 19n/30 - 1/15 is a lower bound for infinitely many values of n. We also prove that the vertex set of any connected claw-free graph of maximum degree at most four, other than an odd cycle longer than three, can be partitioned into two clique-transversal sets. The proofs of both results yield polynomial-time algorithms that find corresponding solutions.
Gray codes avoiding matchings
A (cyclic) n-bit Gray code is a (cyclic) ordering of all 2(n) binary strings of length n such that consecutive strings differ in a single bit. Equivalently, an n-bit Gray code can be viewed as a Hamiltonian path of the n-dimensional hypercube Q(n), and a cyclic Gray code as a Hamiltonian cycle of Q(n). In this paper we study (cyclic) Gray codes avoiding a given set of faulty edges that form a matching. Given a matching M and two vertices u, v of Q(n), n >= 4, our main result provides a necessary and sufficient condition, expressed in terms of forbidden configurations for M, for the existence of a Gray code between u and v that avoids M. As a corollary. we obtain a similar characterization for a cyclic Gray code avoiding M. In particular, in the case that M is a perfect matching, Q(n) has a (cyclic) Gray code that avoids M if and only if Q(n) - M is a connected graph. This complements a recent result of Fink, who proved that every perfect matching of Q(n) can be extended to a Hamiltonian cycle. Furthermore, our results imply that the problem of Hamilionicity of Q(n) with faulty edges, which is NP-complete in general, becomes polynomial for up to 2(n-1) edges provided they form a matching.
Adjoint functors and tree duality
A family T of digraphs is a complete set of obstructions for a digraph H if for an arbitrary digraph G the existence of a homomorphism from G to H is equivalent to the non-existence of a homomorphism from any member of T to G. A digraph H is said to have tree duality if there exists a complete set of obstructions T consisting of orientations of trees. We show that if H has tree duality, then its arc graph delta H also has tree duality, and we derive a family of tree obstructions for delta H from the obstructions for H. Furthermore we generalise our result to right adjoint functors on categories of relational structures. We show that these functors always preserve tree duality, as well as polynomial CSPs and the existence of near-unanimity functions.
Ore and Erdős type conditions for long cycles in balanced bipartite graphs
We conjecture Ore and Erdős type criteria for a balanced bipartite graph of order 2n to contain a long cycle C(2n-2k), where 0 <= k < n/2. For k = 0, these are the classical hamiltonicity criteria of Moon and Moser. The main two results of the paper assert that our conjectures hold for k = 1 as well.
On the chromatic number of some flip graphs
This paper studies the chromatic number of the following four flip graphs (under suitable definitions of a flip): the flip graph of perfect matchings of a complete graph of even order, the flip graph of triangulations of a convex polygon (the associahedron), the flip graph of non-crossing Hamiltonian paths of a set of points in convex position, and the flip graph of triangles in a convex point set. We give tight bounds for the latter two cases and upper bounds for the first two.
Long cycles in hypercubes with distant faulty vertices
In this paper, we study long cycles in induced subgraphs of hypercubes obtained by removing a given set of faulty vertices such that every two faults are distant. First, we show that every induced subgraph of Q(n) with minimum degree n - 1 contains a cycle of length at least 2(n) - 2(f) where f is the number of removed vertices. This length is the best possible when all removed vertices are from the same bipartite class of Q(n). Next, we prove that every induced subgraph of Q(n) obtained by removing vertices of some given set M of edges of Q(n) contains a Hamiltonian cycle if every two edges of M are at distance at least 3. The last result shows that the shell of every linear code with odd minimum distance at least 3 contains a Hamiltonian cycle. In all these results we obtain significantly more tolerable faulty vertices than in the previously known results. We also conjecture that every induced subgraph of Q(n) obtained by removing a balanced set of vertices with minimum distance at least 3 contains a Hamiltonian cycle.
Self-complementing permutations of k-uniform hypergraphs
A k-uniform hypergraph H = ( V; E) is said to be self-complementary whenever it is isomorphic with its complement (H) over bar = ( V; ((V)(k)) - E). Every permutation sigma of the set V such that sigma(e) is an edge of (H) over bar if and only if e is an element of E is called self-complementing. 2-self-comlementary hypergraphs are exactly self complementary graphs introduced independently by Ringel ( 1963) and Sachs ( 1962).
For any positive integer n we denote by lambda(n) the unique integer such that n = 2(lambda(n)) c, where c is odd.
In the paper we prove that a permutation sigma of [1, n] with orbits O-1,..., O-m O m is a self-complementing permutation of a k-uniform hypergraph of order n if and only if there is an integer l >= 0 such that k = a2(l) + s, a is odd, 0 <= s <= 2(l) and the following two conditions hold:
(i)n = b2(l+1) + r,r is an element of {0,..., 2(l) - 1 + s}, and
(ii) Sigma(i:lambda(vertical bar Oi vertical bar)<= l) vertical bar O-i vertical bar <= r.
For k = 2 this result is the very well known characterization of self-complementing permutation of graphs given by Ringel and Sachs.
Independent sets in (P₆, diamond)-free graphs
We prove that on the class of (P6,diamond)-free graphs the Maximum-Weight Independent Set problem and the Minimum-Weight Independent Dominating Set problem can be solved in polynomial time.
Bounds for minimum feedback vertex sets in distance graphs and circulant graphs
For a set D ⊂ Zn, the distance graph Pn(D) has Zn as its vertex set and the edges are between vertices i and j with |i − j| ∈ D. The circulant graph Cn(D) is defined analogously by considering operations modulo n. The minimum feedback vertex set problem consists in finding the smallest number of vertices to be removed in order to cut all cycles in the graph. This paper studies the minimum feedback vertex set problem for some families of distance graphs and circulant graphs depending on the value of D.
On the size of induced acyclic subgraphs in random digraphs
Let D ∈ D(n, p) denote a simple random digraph obtained by choosing each of the (n 2) undirected edges independently with probability 2p and then orienting each chosen edge independently in one of the two directions with equal probability 1/2. Let mas(D) denote the maximum size of an induced acyclic subgraph in D. We obtain tight concentration results on the size of mas(D). Precisely, we show that $mas(D) \le \frac{2}{ln(1-p)^-1} (ln np + 3e)$ almost surely, provided p ≥ W/n for some fixed constant W. This combined with known and new lower bounds shows that (for p satisfying p = ω(1/n) and p ≤ 0.5) $mas(D) = \frac{2(ln np)}{ln(1-p)^-1} (1± o(1))$. This proves a conjecture stated by Subramanian in 2003 for those p such that p = ω(1/n). Our results are also valid for the random digraph obtained by choosing each of the n(n − 1) directed edges independently with probability p.
On the k-restricted structure ratio in planar and outerplanar graphs
A planar k-restricted structure is a simple graph whose blocks are planar and each has at most k vertices. Planar k-restricted structures are used by approximation algorithms for Maximum Weight Planar Subgraph, which motivates this work. The planar k-restricted ratio is the infimum, over simple planar graphs H, of the ratio of the number of edges in a maximum k-restricted structure subgraph of H to the number edges of H. We prove that, as k tends to infinity, the planar k-restricted ratio tends to 1 = 2. The same result holds for the weighted version. Our results are based on analyzing the analogous ratios for outerplanar and weighted outerplanar graphs. Here both ratios tend to 1 as k goes to infinity, and we provide good estimates of the rates of convergence, showing that they differ in the weighted from the unweighted case.
On-line Ramsey numbers for paths and stars
We study on-line version of size-Ramsey numbers of graphs defined via a game played between Builder and Painter: in one round Builder joins two vertices by an edge and Painter paints it red or blue. The goal of Builder is to force Painter to create a monochromatic copy of a fixed graph H in as few rounds as possible. The minimum number of rounds (assuming both players play perfectly) is the on-line Ramsey number r(H) of the graph H. We determine exact values of r(H) for a few short paths and obtain a general upper bound r(Pn) ≤ 4n −7. We also study asymmetric version of this parameter when one of the target graphs is a star Sn with n edges. We prove that r(Sn, H) ≤ n*e(H) when H is any tree, cycle or clique
Progress on the traceability conjecture for oriented graphs
A digraph is k-traceable if each of its induced subdigraphs of order k is traceable. The Traceability Conjecture is that for k ≥ 2 every k-traceable oriented graph of order at least 2k − 1 is traceable. The conjecture has been proved for k ≤ 5. We prove that it also holds for k = 6.
A note on compact and compact circular edge-colorings of graphs
We study two variants of edge-coloring of edge-weighted graphs, namely compact edge-coloring and circular compact edge-coloring. First, we discuss relations between these two coloring models. We prove that every outerplanar bipartite graph admits a compact edge-coloring and that the decision problem of the existence of compact circular edge-coloring is NP-complete in general. Then we provide a polynomial time 1:5-approximation algorithm and pseudo-polynomial exact algorithm for compact circular coloring of odd cycles and prove that it is NP-hard to optimally color these graphs. Finally, we prove that if a path P2 is joined by an edge to an odd cycle then the problem of the existence of a compact circular coloring becomes NP-complete.
Total domination in K₅- and K₆-covered graphs
A graph G is Kr-covered if each vertex of G is contained in a Kr-clique. Let $\gamma_t(G)$ denote the total domination number of G. It has been conjectured that every Kr-covered graph of order n with no Kr-component satisfies $\gamma_t(G) \le \frac{2n}{r+1}$. We prove that this conjecture is true for r = 5 and 6.
Bounded-degree graphs have arbitrarily large queue-number
It is proved that there exist graphs of bounded degree with arbitrarily large queue-number. In particular, for all \Delta ≥ 3 and for all sufficiently large n, there is a simple \Delta-regular n-vertex graph with queue-number at least c√\Delta_n^{1/2-1/\Delta} for some absolute constant c.
Extremal K_(s,t)-free bipartite graphs
In this paper new exact values of the Zarankiewicz function z(m,n;s,t) are obtained assuming certain requirements on the parameters. Moreover, all the corresponding extremal graphs are characterized. Finally, an extension of this problem to 3-partite graphs is studied.
The Laplacian spread of a tree
The Laplacian spread of a graph is defined to be the difference between the largest eigenvalue and the second smallest eigenvalue of the Laplacian matrix of the graph. In this paper, we show that the star is the unique tree with maximal Laplacian spread among all trees of given order, and the path is the unique one with minimal Laplacian spread among all trees of given order.
On hereditary Helly classes of graphs
In graph theory, the Helly property has been applied to families of sets, such as cliques, disks, bicliques, and neighbourhoods, leading to the classes of clique-Helly, disk-Helly, biclique-Helly, neighbourhood-Helly graphs, respectively. A natural question is to determine for which graphs the corresponding Helly property holds, for every induced subgraph. This leads to the corresponding classes of hereditary clique-Helly, hereditary disk-Helly, hereditary biclique-Helly and hereditary neighbourhood-Helly graphs. In this paper, we describe characterizations in terms of families of forbidden subgraphs, for the classes of hereditary biclique-Helly and hereditary neighbourhood-Helly graphs. We consider both open and closed neighbourhoods. The forbidden subgraphs are all of fixed size, implying polynomial time recognition for these classes.
Bounds for minimum feedback vertex sets in distance graphs and circulant graphs
For a set D ⊂ Zn, the distance graph Pn(D) has Zn as its vertex set and the edges are between vertices i and j with |i − j| ∈ D. The circulant graph Cn(D) is defined analogously by considering operations modulo n. The minimum feedback vertex set problem consists in finding the smallest number of vertices to be removed in order to cut all cycles in the graph. This paper studies the minimum feedback vertex set problem for some families of distance graphs and circulant graphs depending on the value of D.
Recurrence among trees with most numerous efficient dominating sets
A dominating set D of vertices in a graph G is called an efficient dominating set if the distance between any two vertices in D is at least three. A tree T of order n is called maximum if T has the largest number of efficient dominating sets among all n-vertex trees. A constructive characterization of all maximum trees is given. Their structure has recurring aspects with period 7. Moreover, the number of efficient dominating sets in maximum n-vertex trees is determined and is exponential. Also the number of maximum n-vertex trees is shown to be bounded below by an increasing exponential function in n.
A lower bound for approximating the Grundy number
The grundy numbering of a graph is the maximum number of colors used by on-line first-fit coloring, under the worst order of arrival of vertices. The grundy numbering problem is to find this ordering. We prove that there is a constant c>1 so that approximating the grundy numbering problem within c is not possible, unless NP ⊆ RP
Tribes of cubic partial cubes
Partial cubes are graphs isometrically embeddable into hypercubes. Three infinite families and a few sporadic examples of cubic partial cubes are known. The concept of a tribe is introduced as means to systematize the known examples and establish relations among them. Efficient methods of computation of tribes are developed and several concrete tribes, that include known, as well as new cubic partial cubes, are computed by hand and with the use of a computer.
Probe split graphs
An undirected graph G=(V,E) is a probe split graph if its vertex set can be partitioned into two sets, N (non-probes) and P (probes) where N is independent and there exists E' ⊆ N× N such that G'=(V,E∪ E') is a split graph. Recently Chang et al. gave an O(V4(V+E)) time recognition algorithm for probe split graphs. In this article we give O(V2+VE) time recognition algorithms and characterisations by forbidden induced subgraphs both for the case when the partition into probes and non-probes is given, and when it is not given.
On the complexity of the balanced vertex ordering problem
We consider the problem of finding a balanced ordering of the vertices of a graph. More precisely, we want to minimise the sum, taken over all vertices v, of the difference between the number of neighbours to the left and right of v. This problem, which has applications in graph drawing, was recently introduced by Biedl et al. [Discrete Applied Math. 148:27―48, 2005]. They proved that the problem is solvable in polynomial time for graphs with maximum degree three, but NP-hard for graphs with maximum degree six. One of our main results is to close the gap in these results, by proving NP-hardness for graphs with maximum degree four. Furthermore, we prove that the problem remains NP-hard for planar graphs with maximum degree four and for 5-regular graphs. On the other hand, we introduce a polynomial time algorithm that determines whetherthere is a vertex ordering with total imbalance smaller than a fixed constant, and a polynomial time algorithm that determines whether a given multigraph with even degrees has an 'almost balanced' ordering.
Approximation and inapproximability results on balanced connected partitions of graphs
Let G=(V,E) be a connected graph with a weight function w: V \to \mathbbZ₊, and let q ≥q 2 be a positive integer. For X⊆ V, let w(X) denote the sum of the weights of the vertices in X. We consider the following problem on G: find a q-partition P=(V₁,V₂, \ldots, V_q) of V such that G[V_i] is connected (1≤q i≤q q) and P maximizes \rm min\w(V_i): 1≤q i≤q q\. This problem is called \textitMax Balanced Connected q-Partition and is denoted by BCP_q. We show that for q≥q 2 the problem BCP_q is NP-hard in the strong sense, even on q-connected graphs, and therefore does not admit a FPTAS, unless \rm P=\rm NP. We also show another inapproximability result for BCP₂ on arbitrary graphs. On q-connected graphs, for q=2 the best result is a \frac43-approximation algorithm obtained by Chleb\'ıková; for q=3 and q=4 we present 2-approximation algorithms. When q is not fixed (it is part of the instance), the corresponding problem is called \textitMax Balanced Connected Partition, and denoted as BCP. We show that BCP does not admit an approximation algorithm with ratio smaller than 6/5, unless \rm P=\rm NP.
Independent sets in graphs with an excluded clique minor
Let G be a graph with n vertices, with independence number α, and with no Kt+1-minor for some t ≥ 5. It is proved that (2α - 1)(2t - 5) ≥ 2n - 5. This improves upon the previous best bound whenever n≥2/5t2.
Complexity results on graphs with few cliques
A graph class has few cliques if there is a polynomial bound on the number of maximal cliques contained in any member of the class. This restriction is equivalent to the requirement that any graph in the class has a polynomial sized intersection representation that satisfies the Helly property. On any such class of graphs, some problems that are NP-complete on general graphs, such as the maximum clique problem and the maximum weighted clique problem, admit polynomial time algorithms. Other problems, such as the vertex clique cover and edge clique cover problems remain NP-complete on these classes. Several classes of graphs which have few cliques are discussed, and the complexity of some partitioning and covering problems are determined for the class of all graphs which have fewer cliques than a given polynomial bound.
On the kth Eigenvalues of Trees with Perfect Matchings
Résumé comportant des formules mathématiques, disponible sur le ficher pdf / Abstract with mathematical formulas, available on pdf file.
Strong chromatic index of products of graphs
The strong chromatic index of a graph is the minimum number of colours needed to colour the edges in such a way that each colour class is an induced matching. In this paper, we present bounds for strong chromatic index of three different products of graphs in term of the strong chromatic index of each factor. For the cartesian product of paths, cycles or complete graphs, we derive sharper results. In particular, strong chromatic indices of d-dimensional grids and of some toroidal grids are given along with approximate results on the strong chromatic index of generalized hypercubes.