Optimal acyclic edge colouring of grid like graphs

We determine the values of the acyclic chromatic index of a class of graphs referred to as d-dimensional partial tori. These are graphs which can be expressed as the cartesian product of d graphs each of which is an induced path or cycle. This class includes some known classes of graphs like d-dimensional meshes, hypercubes, tori, etc. Our estimates are exact except when the graph is a product of a path and a number of odd cycles, in which case the estimates differ by an additive factor of at most 1. Our results are also constructive and provide an optimal (or almost optimal) acyclic edge colouring in polynomial time.     

Graph bisection algorithms with good average case behavior

In the paper, we describe a polynomial time algorithm that, for every input graph, either outputs the minimum bisection of the graph or halts without output. More importantly, we show that the algorithm chooses the former course with high probability for many natural classes of graphs. In particular, for every fixedd≧3, all sufficiently largen and allb=o(n ^{1?1/[(d+1)/2]}), the algorithm finds the minimum bisection for almost alld-regular labelled simple graphs with 2n nodes and bisection widthb. For example, the algorithm succeeds for almost all 5-regular graphs with 2n nodes and bisection widtho(n ^2/3). The algorithm differs from other graph bisection heuristics (as well as from many heuristics for other NP-complete problems) in several respects. Most notably:

1. the algorithm provides exactly the minimum bisection for almost all input graphs with the specified form, instead of only an approximation of the minimum bisection,
2. whenever the algorithm produces a bisection, it is guaranteed to be optimal (i.e., the algorithm also produces a proof that the bisection it outputs is an optimal bisection),
3. the algorithm works well both theoretically and experimentally,
4. the algorithm employs global methods such as network flow instead of local operations such as 2-changes, and
5. the algorithm works well for graphs with small bisections (as opposed to graphs with large bisections, for which arbitrary bisections are nearly optimal).

     

Interval-regular graphs

An interval-regular graph is a connected graph in which, for any two vertices u and v, the number of neighbours of u on all shortest (u, v)-paths equals d(u, v). It is proved that in an interval-regular graph the shortest (u, v)-paths induce a hypercube of dimension d(u, v), for any two vertices u and v. The products of complete graphs are characterized as interval-regular graphs satisfying some extra conditions. The extended odd graphs are introduced as critical example with respect to the results proved.     

Solving the path cover problem on circular-arc graphs by using an approximation algorithm

A path cover of a graph G=(V,E) is a family of vertex-disjoint paths that covers all vertices in V. Given a graph G, the path cover problem is to find a path cover of minimum cardinality. This paper presents a simple O(n)-time approximation algorithm for the path cover problem on circular-arc graphs given a set of n arcs with endpoints sorted. The cardinality of the path cover found by the approximation algorithm is at most one more than the optimal one. By using the result, we reduce the path cover problem on circular-arc graphs to the Hamiltonian cycle and Hamiltonian path problems on the same class of graphs in O(n) time. Hence the complexity of the path cover problem on circular-arc graphs is the same as those of the Hamiltonian cycle and Hamiltonian path problems on circular-arc graphs.     

Isometric path numbers of graphs

An isometric path between two vertices in a graph G is a shortest path joining them. The isometric path number of G, denoted by ip(G), is the minimum number of isometric paths needed to cover all vertices of G. In this paper, we determine exact values of isometric path numbers of complete r-partite graphs and Cartesian products of 2 or 3 complete graphs.     

Algebraic connectivity of directed graphs

We consider a generalization of Fiedler's notion of algebraic connectivity to directed graphs. We show that several properties of Fiedler's definition remain valid for directed graphs and present properties peculiar to directed graphs. We prove inequalities relating the algebraic connectivity to quantities such as the bisection width, maximum directed cut and the isoperimetric number. Finally, we illustrate an application to the synchronization in networks of coupled chaotic systems.     

Classification of subsets with minimal width and dual width in Grassmann, bilinear forms and dual polar graphs

Brouwer, Godsil, Koolen and Martin [Width and dual width of subsets in polynomial association schemes, J. Combin. Theory Ser. A 102 (2003) 255-271] introduced the width w and the dual width w^* of a subset in a distance-regular graph and in a cometric association scheme, respectively, and then derived lower bounds on these new parameters. For instance, subsets with the property w+w^*=d in a cometric distance-regular graph with diameter d attain these bounds. In this paper, we classify subsets with this property in Grassmann graphs, bilinear forms graphs and dual polar graphs. We use this information to establish the Erd?s-Ko-Rado theorem in full generality for the first two families of graphs.     

Algebraic connectivity of directed graphs

We consider a generalization of Fiedler's notion of algebraic connectivity to directed graphs. We show that several properties of Fiedler's definition remain valid for directed graphs and present properties peculiar to directed graphs. We prove inequalities relating the algebraic connectivity to quantities such as the bisection width, maximum directed cut and the isoperimetric number. Finally, we illustrate an application to the synchronization in networks of coupled chaotic systems.     

The diameter of bipartite distance-regular graphs

It is shown that any bipartite distance-regular graph with finite valency k and at least one cycle is finite, with diameter d and girth g satisfying $\text{d≤}\text{(k?1)(g?2)}\text{2+1}$. In particular, the number of bipartite distance-regular graphs with fixed valency and girth is finite.     

Breaking the rhythm on graphs

We study graph colorings avoiding periodic sequences with large number of blocks on paths. The main problem is to decide, for a given class of graphs F, if there are absolute constants t,k such that any graph from the class has a t-coloring with no k identical blocks in a row appearing on a path. The minimum t for which there is some k with this property is called the rhythm threshold of F, denoted by t(F). For instance, we show that the rhythm threshold of graphs of maximum degree at most d is between (d+1)/2 and d+1. We give several general conditions for finiteness of t(F), as well as some connections to existing chromatic parameters. The question whether the rhythm threshold is finite for planar graphs remains open.     

Jump number of dags having Dilworth number 2

The jump number, denoted by σ, of a directed acyclic graph (dag) G, is the minimum number of arcs that have to be added to G such that the resulting graph is still acyclic and has a hamiltonian path.We study here the particular class of dags having an induced partial order of width 2, and give a characterization of such graphs with σ(G)=i. This yields immediately a polynomial algorithm to compute the jump number in this particular class.     

Rainbow Connection and Graph Products

A path in an edge colored graph G is called a rainbow path if all its edges have pairwise different colors. Then G is rainbow connected if there exists a rainbow path between every pair of vertices of G and the least number of colors needed to obtain a rainbow connected graph is the rainbow connection number. If we demand that there must exist a shortest rainbow path between every pair of vertices, we speak about strongly rainbow connected graph and the strong rainbow connection number. In this paper we study the (strong) rainbow connection number on the direct, strong, and lexicographic product and present several upper bounds for these products that are attained by many graphs. Several exact results are also obtained.     

On minimum bisection and related cut problems in trees and tree‐like graphs

Minimum bisection denotes the NP‐hard problem to partition the vertex set of a graph into two sets of equal sizes while minimizing the width of the bisection, which is defined as the number of edges between these two sets. It is intuitively clear that graphs with a somewhat linear structure are easy to bisect, and therefore our aim is to relate the minimum bisection width of a bounded‐degree graph G to a parameter that measures the similarity between G and a path. First, for trees, we use the diameter and show that the minimum bisection width of every tree T on n vertices satisfies . Second, we generalize this to arbitrary graphs with a given tree decomposition  and give an upper bound on the minimum bisection width that depends on how close  is to a path decomposition. Moreover, we show that a bisection satisfying our general bound can be computed in time proportional to the encoding length of the tree decomposition when the latter is provided as input.     

Lower bounds on the independence number in terms of the degrees

Wei discovered that the independence number of a graph G is at least Σ_v(1 + d(v))^?1. It is proved here that if G is a connected triangle-free graph on n ≥ 3 vertices and if G is neither an odd cycle nor an odd path, then the bound above can be increased by $\text{n}\text{Δ(Δ + 1)}$, where Δ is the maximum degree. This new bound is sharp for even cycles and for three other graphs. These results relate nicely to some algorithms for finding large independent sets. They also have a natural matrix theory interpretation. A survey of other known lower bounds on the independence number is presented.     

The 2‐dimensional rigidity of certain families of graphs

Laman's characterization of minimally rigid 2‐dimensional generic frameworks gives a matroid structure on the edge set of the underlying graph, as was first pointed out and exploited by L. Lovász and Y. Yemini. Global rigidity has only recently been characterized by a combination of two results due to T. Jordán and the first named author, and R. Connelly, respectively. We use these characterizations to investigate how graph theoretic properties such as transitivity, connectivity and regularity influence (2‐dimensional generic) rigidity and global rigidity and apply some of these results to reveal rigidity properties of random graphs. In particular, we characterize the globally rigid vertex transitive graphs, and show that a random d‐regular graph is asymptotically almost surely globally rigid for all d ≥ 4. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 154–166, 2007     

The heterochromatic cycles in edge-colored graphs

Given a graph and an edge coloring C of G, a heterochromatic cycle of G is a cycle in which any pair of edges have distinct colors. Let d ^c (v), named the color degree of a vertex v, be the maximum number of distinct colored edges incident with v. In this paper, we give several sufficient conditions for the existence of heterochromatic cycles in edge-colored graphs.     

The geometry of t‐spreads in k‐walk‐regular graphs

A graph is walk‐regular if the number of closed walks of length ? rooted at a given vertex is a constant through all the vertices for all ?. For a walk‐regular graph G with d+1 different eigenvalues and spectrally maximum diameter D=d, we study the geometry of its d‐spreads, that is, the sets of vertices which are mutually at distance d. When these vertices are projected onto an eigenspace of its adjacency matrix, we show that they form a simplex (or tetrahedron in a three‐dimensional case) and we compute its parameters. Moreover, the results are generalized to the case of k‐walk‐regular graphs, a family which includes both walk‐regular and distance‐regular graphs, and their t‐spreads or vertices at distance t from each other. © 2009 Wiley Periodicals, Inc. J Graph Theory 64:312–322, 2010     

Bisecting de Bruijn and Kautz graphs

De Bruijn and Kautz graphs have been intensively studied as perspective interconnection networks of massively parallel computers. One of the crucial parameters of an interconnection network is its bisection width. It has an influence on both communication properties of the network and the algorithmic design. We prove optimal bounds on the edge and vertex bisection widths of the k-ary n-dimensional de Bruijn digraph. This generalizes known results for k = 2 and improves the upper bound for the vertex bisection width. We extend the method to prove optimal upper and lower bounds on the edge and vertex bisection widths of Kautz graphs.     

The basis number of the n-cube

The basis number of a graph G is defined as the least integer k such that G has a k-fold basis for its cycle space. MacLane (Fund. Math.28 (1937), 22–32) has shown that a graph is planar if and only if its basis number is ≤2. The basis numbers of certain classes of nonplanar graphs have been previously investigated. The basis number of the n-cube for every n is determined in the paper.     

On the theta number of powers of cycle graphs

We give a closed formula for Lovász’s theta number of the powers of cycle graphs C _k ^d?1 and of their complements, the circular complete graphs K _k/d . As a consequence, we establish that the circular chromatic number of a circular perfect graph is computable in polynomial time. We also derive an asymptotic estimate for the theta number of C _k ^d .