Computation of best possible low degree expanders

We present an algorithm for computing a best possible bipartite cubic expander for a given number of vertices. Such graphs are needed in many applications and are also the basis for many results in theoretical computer science. Known construction methods for expander graphs yield expanders that have a fairly poor expansion compared to the best possible expansion. Our algorithm is based on a lemma which allows to calculate an upper bound for the expansion of cubic bipartite graphs.     

Graphs having distance-n domination number half their order

For any positive integer n and any graph G a set D of vertices of G is a distance-n dominating set, if every vertex vV(G)−D has exactly distance n to at least one vertex in D. The distance-n domination number γ_=n(G) is the smallest number of vertices in any distance-n dominating set. If G is a graph of order p and each vertex in G has distance n to at least one vertex in G, then the distance-n domination number has the upper bound p/2 as Ore's upper bound on the classical domination number. In this paper, a characterization is given for graphs having distance-n domination number equal to half their order, when the diameter is greater or equal 2n−1. With this result we confirm a conjecture of Boland, Haynes, and Lawson.     

The integrity of a cubic graph

Integrity, a measure of network reliability, is defined as

where G is a graph with vertex set V and m(G−S) denotes the order of the largest component of G−S. We prove an upper bound of the following form on the integrity of any cubic graph with n vertices:

Moreover, there exist an infinite family of connected cubic graphs whose integrity satisfies a linear lower bound I(G)>βn for some constant β. We provide a value for β, but it is likely not best possible. To prove the upper bound we first solve the following extremal problem. What is the least number of vertices in a cubic graph whose removal results in an acyclic graph? The solution (with a few minor exceptions) is that n/3 vertices suffice and this is best possible.     

Matching extension and minimum degree

Let G be a simple connected graph on 2n vertices with a perfect matching. For a given positive integer k, 1 k n − 1, G is k-extendable if for every matching M of size k in G, there exists a perfect matching in G containing all the edges of M. The problem that arises is that of characterizing k-extendable graphs. In this paper, we establish a necessary condition, in terms of minimum degree, for k-extendable graphs. Further, we determine the set of realizable values for minimum degree of k-extendable graphs. In addition, we establish some results on bipartite graphs including a sufficient condition for a bipartite graph to be k-extendable.     

Covering a graph by complete bipartite graphs

We prove the following theorem: the edge set of every graph G on n vertices can be partitioned into the disjoint union of complete bipartite graphs such that each vertex is contained by at most c(n/log n) of the bipartite graphs.     

The DFS-heuristic for orthogonal graph drawing

In this paper, we present a new heuristic for orthogonal graph drawings, which creates drawings by performing a depth-first search and placing the nodes in the order they are encountered. This DFS-heuristic works for graphs with arbitrarily high degrees, and particularly well for graphs with maximum degree 3. It yields drawings with at most one bend per edge, and a total number of m−n+1 bends for a graph with n nodes and m edges; this improves significantly on the best previous bound of m−2 bends.     

Recognizing Knödel graphs

Knödel graphs form a class of bipartite incident-graph of circulant digraphs. This class has been extensively studied for the purpose of fast communications in networks, and it has deserved a lot of attention in this context. In this paper, we show that there exists an O(n log⁵ n)-time algorithm to recognize Knödel graphs of order 2n. The algorithm is based on a characterization of the cycles of length six in these graphs (bipartite incident-graphs of circulant digraphs always have cycles of length six). A consequence of our result is that the circulant digraphs whose chords are the power of two minus one can be recognized in O(n log⁵ n) time.     

Triangle-free graphs and forbidden subgraphs

The relation of chromatic aspects and the existence of certain induced subgraphs of a triangle-free graph will be investigated. Based on a characterization statement of Pach, some results on the chromatic number of triangle-free graphs with certain forbidden induced subgraphs will be refined by describing their structure in terms of homomorphisms. In particular, we introduce chordal triangle-free graphs as a natural superclass of chordal bipartite graphs and describe the structure of the maximal triangle-free members. Finally, we improve on the upper bound for the chromatic number of triangle-free sK₂-free graphs by 1 for s2 giving the tight bound for s=3.     

A note on minimum degree conditions for supereulerian graphs

A graph is called supereulerian if it has a spanning closed trail. Let G be a 2-edge-connected graph of order n such that each minimal edge cut SE(G) with |S|3 satisfies the property that each component of G−S has order at least (n−2)/5. We prove that either G is supereulerian or G belongs to one of two classes of exceptional graphs. Our results slightly improve earlier results of Catlin and Li. Furthermore, our main result implies the following strengthening of a theorem of Lai within the class of graphs with minimum degree δ4: If G is a 2-edge-connected graph of order n with δ(G)4 such that for every edge xyE(G) , we have max{d(x),d(y)}(n−2)/5−1, then either G is supereulerian or G belongs to one of two classes of exceptional graphs. We show that the condition δ(G)4 cannot be relaxed.     

An infinite family of cubic edge- but not vertex-transitive graphs

An infinite family of cubic edge- but not vertex-transitive graphs is constructed. The graphs are obtained as regular -covers of K_3,3 where n=p₁^e₁p₂^e₂p_k^e_k where p_i are distinct primes congruent to 1 modulo 3, and e_i1. Moreover, it is proved that the Gray graph (of order 54) is the smallest cubic edge- but not vertex-transitive graph.     

Primitive graphs with given exponents and minimum number of edges

A graph G = (V, E) on n vertices is primitive if there is a positive integer k such that for each pair of vertices u, v of G, there is a walk of length k from u to v. The minimum value of such an integer, k, is the exponent, exp(G), of G. In this paper, we find the minimum number, h(n, k), of edges of a simple graph G on n vertices with exponent k, and we characterize all graphs which have h(n, k) edges when k is 3 or even.     

Connectivity of generalized prisms over G

The problem of building larger graphs with a given graph as an induced subgraph is one which can arise in various applications and in particular can be important when constructing large communications networks from smaller ones. What one can conclude from this paper is that generalized prisms over G may provide an important such construction because the connectivity of the newly created graph is larger than that of the original (connected) graph, regardless of the permutation used.

For a graph G with vertices labeled 1,2,…, n and a permutation in S_n, the generalized prisms over G, (G) (also called a permutation graph), consists of two copies of G, say G_x and G_y, along with the edges (x_i, y_(i), for 1≤i≤n. The purpose of this paper is to examine the connectivity of generalized prisms over G. In particular, upper and lower bounds are found. Also, the connectivity and edge-connectivity are determined for generalized prisms over trees, cycles, wheels, n-cubes, complete graphs, and complete bipartite graphs. Finally, the connectivity of the generalized prism over G, (G), is determined for all in the automorphism group of G.     

Graph drawings with few slopes

The slope-number of a graph G is the minimum number of distinct edge slopes in a straight-line drawing of G in the plane. We prove that for Δ5 and all large n, there is a Δ-regular n-vertex graph with slope-number at least . This is the best known lower bound on the slope-number of a graph with bounded degree. We prove upper and lower bounds on the slope-number of complete bipartite graphs. We prove a general upper bound on the slope-number of an arbitrary graph in terms of its bandwidth. It follows that the slope-number of interval graphs, cocomparability graphs, and AT-free graphs is at most a function of the maximum degree. We prove that graphs of bounded degree and bounded treewidth have slope-number at most . Finally we prove that every graph has a drawing with one bend per edge, in which the number of slopes is at most one more than the maximum degree. In a companion paper, planar drawings of graphs with few slopes are also considered.     

Dominating the complements of bounded tolerance graphs and the complements of trapezoid graphs

We investigate the complexity of several domination problems on the complements of bounded tolerance graphs and the complements of trapezoid graphs. We describe an O(n² log⁵ n) time and O(n²) space algorithm to solve the domination problem on the complement of a bounded tolerance graph, given a square embedding of that graph. We also prove that domination, connected domination and total domination are all NP-complete on co-trapezoid graphs.     

Drawings of planar graphs with few slopes and segments

We study straight-line drawings of planar graphs with few segments and few slopes. Optimal results are obtained for all trees. Tight bounds are obtained for outerplanar graphs, 2-trees, and planar 3-trees. We prove that every 3-connected plane graph on n vertices has a plane drawing with at most segments and at most 2n slopes. We prove that every cubic 3-connected plane graph has a plane drawing with three slopes (and three bends on the outerface). In a companion paper, drawings of non-planar graphs with few slopes are also considered.     

Embedding of circulant graphs and generalized Petersen graphs on projective plane

Both the circulant graph and the generalized Petersen graph are important types of graphs in graph theory. In this paper, the structures of embeddings of circulant graph C(2n + 1; {1, n}) on the projective plane are described, the number of embeddings of C(2n + 1; {1, n}) on the projective plane follows, then the number of embeddings of the generalized Petersen graph P(2n +1, n) on the projective plane is deduced from that of C(2n +1; {1, n}), because C(2n + 1;{1, n}) is a minor of P(2n + 1, n), their structures of embeddings have relations. In the same way, the number of embeddings of the generalized Petersen graph P(2n, 2) on the projective plane is also obtained.     

Recognizing graphs without asteroidal triples

We consider the problem of recognizing AT-free graphs. Although there is a simple O(n³) algorithm, no faster method for solving this problem had been known. Here we give three different algorithms which have a better time complexity for graphs which are sparse or have a sparse complement; in particular we give algorithms which recognize AT-free graphs in , , and O(n^2.82+nm). In addition we give a new characterization of graphs with bounded asteroidal number by the help of the knotting graph, a combinatorial structure which was introduced by Gallai for considering comparability graphs.     

Hamiltonicity in vertex envelopes of plane cubic graphs

In this paper we study a graph operation which produces what we call the “vertex envelope” G^∗_V from a graph G. We apply it to plane cubic graphs and investigate the hamiltonicity of the resulting graphs, which are also cubic. To this end, we prove a result giving a necessary and sufficient condition for the existence of hamiltonian cycles in the vertex envelopes of plane cubic graphs. We then use these conditions to identify graphs or classes of graphs whose vertex envelopes are either all hamiltonian or all non-hamiltonian, paying special attention to bipartite graphs. We also show that deciding if a vertex envelope is hamiltonian is NP-complete, and we provide a polynomial algorithm for deciding if a given cubic plane graph is a vertex envelope.     

Multicolored forests in complete bipartite graphs

If the edges of a graph G are colored using k colors, we consider the color distribution for this coloring a=(a₁,a₂,…,a_k), in which a_i denotes the number of edges of color i for i=1,2,…,k. We find inequalities and majorization conditions on color distributions of the complete bipartite graph K_n,n which guarantee the existence of multicolored subgraphs: in particular, multicolored forests and trees. We end with a conjecture on partitions of K_n,n into multicolored trees.     

Balanced Cayley graphs and balanced planar graphs

A balanced graph is a bipartite graph with no induced circuit of length . These graphs arise in integer linear programming. We focus on graph-algebraic properties of balanced graphs to prove a complete classification of balanced Cayley graphs on abelian groups. Moreover, in this paper, we prove that there is no cubic balanced planar graph. Finally, some remarkable conjectures for balanced regular graphs are also presented. The graphs in this paper are simple.