Asymptotic approximation for the number of <Emphasis Type="Italic">n</Emphasis>-vertex graphs of given diameter

We prove that, for fixed k ≥ 3, the following classes of labeled n-vertex graphs are asymptotically equicardinal: graphs of diameter k, connected graphs of diameter at least k, and (not necessarily connected) graphs with a shortest path of length at least k. An asymptotically exact approximation of the number of such n-vertex graphs is obtained, and an explicit error estimate in the approximation is found. Thus, the estimates are improved for the asymptotic approximation of the number of n-vertex graphs of fixed diameter k earlier obtained by Füredi and Kim. It is shown that almost all graphs of diameter k have a unique pair of diametrical vertices but almost all graphs of diameter 2 have more than one pair of such vertices.     

Flow-Critical Graphs

In this paper we introduce the concept of k-flow-critical graphs. These are graphs that do not admit a k-flow but such that any smaller graph obtained from it by contraction of edges or of pairs of vertices is k-flowable. Any minimal counter-example for Tutte's 3-Flow and 5-Flow Conjectures must be 3-flow-critical and 5-flow-critical, respectively. Thus, any progress towards establishing good characterizations of k-flow-critical graphs can represent progress in the study of these conjectures. We present some interesting properties satisfied by k-flow-critical graphs discovered recently.     

Graphs Without Large Apples and the Maximum Weight Independent Set Problem

An apple A _k is the graph obtained from a chordless cycle C _k of length k ≥ 4 by adding a vertex that has exactly one neighbor on the cycle. The class of apple-free graphs is a common generalization of claw-free graphs and chordal graphs, two classes enjoying many attractive properties, including polynomial-time solvability of the maximum weight independent set problem. Recently, Brandstädt et al. showed that this property extends to the class of apple-free graphs. In the present paper, we study further generalization of this class called graphs without large apples: these are (A _k , A _k+1, . . .)-free graphs for values of k strictly greater than 4. The complexity of the maximum weight independent set problem is unknown even for k = 5. By exploring the structure of graphs without large apples, we discover a sufficient condition for claw-freeness of such graphs. We show that the condition is satisfied by bounded-degree and apex-minor-free graphs of sufficiently large tree-width. This implies an efficient solution to the maximum weight independent set problem for those graphs without large apples, which either have bounded vertex degree or exclude a fixed apex graph as a minor.     

Minimum monopoly in regular and tree graphs

In this paper we consider a graph optimization problem called minimum monopoly problem, in which it is required to find a minimum cardinality set S⊆V, such that, for each u∈V, |N[u]∩S|?|N[u]|/2 in a given graph G=(V,E). We show that this optimization problem does not have a polynomial-time approximation scheme for k-regular graphs (k?5), unless P=NP. We show this by establishing two L-reductions (an approximation preserving reduction) from minimum dominating set problem for k-regular graphs to minimum monopoly problem for 2k-regular graphs and to minimum monopoly problem for (2k-1)-regular graphs, where k?3. We also show that, for tree graphs, a minimum monopoly set can be computed in linear time.     

Polar cographs

Polar graphs are a natural extension of some classes of graphs like bipartite graphs, split graphs and complements of bipartite graphs. A graph is (s,k)-polar if there exists a partition A,B of its vertex set such that A induces a complete s-partite graph (i.e., a collection of at most s disjoint stable sets with complete links between all sets) and B a disjoint union of at most k cliques (i.e., the complement of a complete k-partite graph).Recognizing a polar graph is known to be NP-complete. These graphs have not been extensively studied and no good characterization is known. Here we consider the class of polar graphs which are also cographs (graphs without induced path on four vertices). We provide a characterization in terms of forbidden subgraphs. Besides, we give an algorithm in time O(n) for finding a largest induced polar subgraph in cographs; this also serves as a polar cograph recognition algorithm. We examine also the monopolar cographs which are the (s,k)-polar cographs where min(s,k)?1. A characterization of these graphs by forbidden subgraphs is given. Some open questions related to polarity are discussed.     

New families of hypohamiltonian graphs

We construct three new infinite families of hypohamiltonian graphs having respectively 3k+1 vertices (k?3), 3k vertices (k?5) and 5k vertices (k?4); in particular, we exhibit a hypohamiltonian graph of order 19 and a cubic hypohamiltonian graph of order 20, the existence of which was still in doubt. Using these families, we get a lower bound for the number of non-isomorphic hypohamiltonian graphs of order 3k and 5k. We also give an example of an infinite graph G having no two-way infinite hamiltonian path, but in which every vertex-deleted subgraph G - x has such a path.     

The basis number of a graph

MacLane proved that a graph is planar if and only if it has a 2-fold basis for its cycle space. We define the basis number of a graph G to be the least integer k such that G has a k-fold basis for its cycle space. We investigate the basis number of the complete graphs, complete bipartite graphs, and the n-cube.     

Optimal K-secure graphs

We wish to design a resistance movement in such a way that k subversions and the resulting betrayals do not totally destroy our network. Such graphs will be called k-secure. Subject to this restriction we determine which graphs minimize the expected number of betrayals.     

k-noncrossing and k-nonnesting graphs and fillings of Ferrers diagrams

We study the distribution of k-crossings and k-nestings and other patterns in ordered graphs by using fillings of Ferrers diagrams. The main result states that there are as many graphs without k-crossings as without k-nestings. We also show that studying equirrestrictive patterns in ordered graphs is equivalent to studying equirrestrictive matrices in fillings of Ferrers diagrams.     

Contraction obstructions for treewidth

We provide two parameterized graphs Γk, Πk with the following property: for every positive integer k, there is a constant ck such that every graph G with treewidth at least ck, contains one of Kk, Γk, Πk as a contraction, where Kk is a complete graph on k vertices. These three parameterized graphs can be seen as “obstruction patterns” for the treewidth with respect to the contraction partial ordering. We also present some refinements of this result along with their algorithmic consequences.     

Acyclic improper colouring of graphs with maximum degree 4

A k-colouring(not necessarily proper) of vertices of a graph is called acyclic, if for every pair of distinct colours i and j the subgraph induced by the edges whose endpoints have colours i and j is acyclic. We consider acyclic k-colourings such that each colour class induces a graph with a given(hereditary) property. In particular, we consider acyclic k-colourings in which each colour class induces a graph with maximum degree at most t, which are referred to as acyclic t-improper k-colourings. The acyclic t-improper chromatic number of a graph G is the smallest k for which there exists an acyclic t-improper k-colouring of G. We focus on acyclic colourings of graphs with maximum degree 4. We prove that 3 is an upper bound for the acyclic 3-improper chromatic number of this class of graphs. We also provide a non-trivial family of graphs with maximum degree4 whose acyclic 3-improper chromatic number is at most 2, namely, the graphs with maximum average degree at most 3. Finally, we prove that any graph G with Δ(G) 4 can be acyclically coloured with 4 colours in such a way that each colour class induces an acyclic graph with maximum degree at most 3.     

A Family of Clique Divergent Graphs with Linear Growth

We present an infinite set A of finite graphs such that for any graph G e A the order | V(k ⁿ (G))| of the n-th iterated clique graph k ⁿ (G) is a linear function of n. We also give examples of graphs G such that | V(k ⁿ(G))| is a polynomial of any given positive degree.     

Graphs with the maximum or minimum number of 1-factors

Recently Alon and Friedland have shown that graphs which are the union of complete regular bipartite graphs have the maximum number of 1-factors over all graphs with the same degree sequence. We identify two families of graphs that have the maximum number of 1-factors over all graphs with the same number of vertices and edges: the almost regular graphs which are unions of complete regular bipartite graphs, and complete graphs with a matching removed. The first family is determined using the Alon and Friedland bound. For the second family, we show that a graph transformation which is known to increase network reliability also increases the number of 1-factors. In fact, more is true: this graph transformation increases the number of k-factors for all k≥1, and “in reverse” also shows that in general, threshold graphs have the fewest k-factors. We are then able to determine precisely which threshold graphs have the fewest 1-factors. We conjecture that the same graphs have the fewest k-factors for all k≥2 as well.     

Mutual exclusion scheduling with interval graphs or related classes. Part II

This paper is the second part of a study devoted to the mutual exclusion scheduling problem. Given a simple and undirected graph G and an integer k, the problem is to find a minimum coloring of G such that each color is used at most k times. The cardinality of such a coloring is denoted by χ(G,k). When restricted to interval graphs or related classes like circular-arc graphs and tolerance graphs, the problem has some applications in workforce planning. Unfortunately, the problem is shown to be NP-hard for interval graphs, even if k is a constant greater than or equal to four [H.L. Bodlaender, K. Jansen, Restrictions of graph partition problems. Part I. Theoret. Comput. Sci. 148 (1995) 93-109]. In this paper, the problem is approached from a different point of view by studying a non-trivial and practical sufficient condition for optimality. In particular, the following proposition is demonstrated: if an interval graph G admits a coloring such that each color appears at least k times, then χ(G,k)=⌈n/k⌉. This proposition is extended to several classes of graphs related to interval graphs. Moreover, all our proofs are constructive and provide efficient algorithms to solve the MES problem for these graphs, given a coloring satisfying the condition in input.     

R-domination on block graphs

The k-domination problem is to select a minimum cardinality vertex set D of a graph G such that every vertex of G is within distance k from some vertex of D. We consider a generalization of the k-domination problem, called the R-domination problem. A linear algorithm is presented that solves this problem for block graphs. Our algorithm is a generalization of Slater's algorithm [12], which is applicable for forest graphs.     

Improper colouring of (random) unit disk graphs

For any graph G, the k-improper chromatic numberχ^k(G) is the smallest number of colours used in a colouring of G such that each colour class induces a subgraph of maximum degree k. We investigate χ^k for unit disk graphs and random unit disk graphs to generalise results of McDiarmid and Reed [Colouring proximity graphs in the plane, Discrete Math. 199(1-3) (1999) 123-137], McDiarmid [Random channel assignment in the plane, Random Structures Algorithms 22(2) (2003) 187-212], and McDiarmid and Müller [On the chromatic number of random geometric graphs, submitted for publication].     

On k-planar crossing numbers

The k-planar crossing number of a graph is the minimum number of crossings of its edges over all possible drawings of the graph in k planes. We propose algorithms and methods for k-planar drawings of general graphs together with lower bound techniques. We give exact results for the k-planar crossing number of K_2k+1,q, for k?2. We prove tight bounds for complete graphs. We also study the rectilinear k-planar crossing number.     

On distance-3 matchings and induced matchings

For a finite undirected graph G=(V,E) and positive integer k≥1, an edge set M⊆E is a distance-k matching if the pairwise distance of edges in M is at least k in G. For k=1, this gives the usual notion of matching in graphs, and for general k≥1, distance-k matchings were called k-separated matchings by Stockmeyer and Vazirani. The special case k=2 has been studied under the names induced matching (i.e., a matching which forms an induced subgraph in G) by Cameron and strong matching by Golumbic and Laskar in various papers.Finding a maximum induced matching is NP-complete even on very restricted bipartite graphs and on claw-free graphs but it can be done efficiently on various classes of graphs such as chordal graphs, based on the fact that an induced matching in G corresponds to an independent vertex set in the square L(G)² of the line graph L(G) of G which, by a result of Cameron, is chordal for any chordal graph G.We show that, unlike for k=2, for a chordal graph G, L(G)³ is not necessarily chordal, and finding a maximum distance-3 matching, and more generally, finding a maximum distance-(2k+1) matching for k≥1, remains NP-complete on chordal graphs. For strongly chordal graphs and interval graphs, however, the maximum distance-k matching problem can be solved in polynomial time for every k≥1. Moreover, we obtain various new results for maximum induced matchings on subclasses of claw-free graphs.     

Construction for bicritical graphs and k-extendable bipartite graphs

A graph G is said to be bicritical if G-u-v has a perfect matching for every choice of a pair of points u and v. Bicritical graphs play a central role in decomposition theory of elementary graphs with respect to perfect matchings. As Plummer pointed out many times, the structure of bicritical graphs is far from completely understood. This paper presents a concise structure characterization on bicritical graphs in terms of factor-critical graphs and transversals of hypergraphs. A connected graph G with at least 2k+2 points is said to be k-extendable if it contains a matching of k lines and every such matching is contained in a perfect matching. A structure characterization for k-extendable bipartite graphs is given in a recursive way. Furthermore, this paper presents an O(mn) algorithm for determining the extendability of a bipartite graph G, the maximum integer k such that G is k-extendable, where n is the number of points and m is the number of lines in G.     

The weak limit of Ising models on locally tree-like graphs

We consider the Ising model with inverse temperature β and without external field on sequences of graphs G _n which converge locally to the k-regular tree. We show that for such graphs the Ising measure locally weakly converges to the symmetric mixture of the Ising model with + boundary conditions and the ? boundary conditions on the k-regular tree with inverse temperature β. In the case where the graphs G _n are expanders we derive a more detailed understanding by showing convergence of the Ising measure conditional on positive magnetization (sum of spins) to the + measure on the tree.