Bipartite density of cubic graphs

We first obtain the exact value for bipartite density of a cubic line graph on n vertices. Then we give an upper bound for the bipartite density of cubic graphs in terms of the smallest eigenvalue of the adjacency matrix. In addition, we characterize, except in the case n=20, those graphs for which the upper bound is obtained.     

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.     

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.     

Bipartite dimensions and bipartite degrees of graphs

A cover (bipartite) of a graph G is a family of complete bipartite subgraphs of G whose edges cover G's edges. G'sbipartite dimension d(G) is the minimum cardinality of a cover, and its bipartite degree η(G) is the minimum over all covers of the maximum number of covering members incident to a vertex. We prove that d(G) equals the Boolean interval dimension of the irreflexive complement of G, identify the 21 minimal forbidden induced subgraphs for d 2, and investigate the forbidden graphs for d n that have the fewest vertices. We note that for complete graphs, d(K_n) = [log₂n], η(K_n) = d(K_n) for n 16, and η(K_n) is unbounded. The list of minimal forbidden induced subgraphs for η 2 is infinite. We identify two infinite families in this list along with all members that have fewer than seven vertices.     

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.     

The chromatic difference sequence of the Cartesian product of graphs

The chromatic difference sequence cds(G) of a graph G with chromatic number n is defined by cds(G) = (a(1), a(2),…, a(n)) if the sum of a(1), a(2),…, a(t) is the maximum number of vertices in an induced t-colorable subgraph of G for t = 1, 2,…, n. The Cartesian product of two graphs G and H, denoted by G□H, has the vertex set V(G□H = V(G) x V(H) and its edge set is given by (x₁, y₁)(x₂, y₂) ε E(G□H) if either x₁ = x₂ and y₁ y₂ ε E(H) or y₁ = y₂ and x₁x₂ ε E(G).

We obtained four main results: the cds of the product of bipartite graphs, the cds of the product of graphs with cds being nondrop flat and first-drop flat, the non-increasing theorem for powers of graphs and cds of powers of circulant graphs.     

Polynomial algorithms for (integral) maximum two-flows in vertex edge-capacitated planar graphs

In this paper we study the maximum two-flow problem in vertex- and edge-capacitated undirected ST₂-planar graphs, that is, planar graphs where the vertices of each terminal pair are on the same face. For such graphs we provide an O(n) algorithm for finding a minimum two-cut and an O(n log n) algorithm for determining a maximum two-flow and show that the value of a maximum two-flow equals the value of a minimum two-cut. We further show that the flow obtained is half-integral and provide a characterization of edge and vertex capacitated ST₂-planar graphs that guarantees a maximum two-flow that is integral. By a simple variation of our maximum two-flow algorithm we then develop, for ST₂-planar graphs with vertex and edge capacities, an O(n log n) algorithm for determining an integral maximum two-flow of value not less than the value of a maximum two-flow minus one.     

Partition of a directed bipartite graph into two directed cycles

Let D = (V₁, V₂; A) be a directed bipartite graph with |V₁| = |V₂| = n 2. Suppose that d_D(x) + d_D(y) 3n + 1 for all x ε V₁ and y ε V₂. Then D contains two vertex-disjoint directed cycles of lengths 2n₁ and 2n₂, respectively, for any positive integer partition n = n₁ + n₂. Moreover, the condition is sharp for even n and nearly sharp for odd n.     

On the spanning tree packing number of a graph: a survey

The spanning tree packing number or STP number of a graph G is the maximum number of edge-disjoint spanning trees contained in G. We use an observation of Paul Catlin to investigate the STP numbers of several families of graphs including quasi-random graphs, regular graphs, complete bipartite graphs, cartesian products and the hypercubes.     

Minimal least eigenvalue of connected graphs of order n and size m = n + k (5≤k≤8)

The least eigenvalue of a connected graph is the least eigenvalue of its adjacency matrix. We characterize the connected graphs of order n and size n + k (5≤k≤8 and n>k + 5) with the minimal least eigenvalue.     

A new infinite series of regular uniformly geodetic code graphs

We construct vertex-transitive graphs Γ, regular of valency k=n²+n+1 on vertices, with integral spectrum, possessing a distinguished complete matching such that contracting the edges of this matching yields the Johnson graph J(2n, n) (of valency n²). These graphs are uniformly geodetic in the sense of Cook and Pryce (1983) (F-geodetic in the sense of Ceccharini and Sappa (1986)), i.e., the number of geodesics between any two vertices only depends on their distance (and equals 4 when this distance is two). They are counterexamples to Theorem 3.15.1 of [1], and we show that there are no other counterexamples.     

Weighted domination in triangle-free graphs

A weighted graph (G,w) is a graph G together with a positive weight-function on its vertex set w : V(G)→R^>0. The weighted domination number γ_w(G) of (G,w) is the minimum weight w(D)=∑_vDw(v) of a set DV(G) such that every vertex xV(D)−D has a neighbor in D. If ∑_vV(G)w(v)=|V(G)|, then we speak of a normed weighted graph. Recently, we proved that

for normed weighted bipartite graphs (G,w) of order n such that neither G nor the complement has isolated vertices. In this paper we will extend these Nordhaus–Gaddum-type results to triangle-free graphs.     

Maximum number of edges in a critically k-connected graph

A k-connected graph G is said to be critically k-connected if G−v is not k-connected for any vV(G). We show that if n,k are integers with k4 and nk+2, and G is a critically k-connected graph of order n, then |E(G)|n(n−1)/2−p(n−k)+p²/2, where p=(n/k)+1 if n/k is an odd integer and p=n/k otherwise. We also characterize extremal graphs.     

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.     

A bijective proof of an identity for noncrossing graphs

We give a bijective proof for the identity a_n+2=8b_n, where a_n is the number of noncrossing simple graphs with n (possibly isolated) vertices and b_n is the number of noncrossing graphs without isolated vertices and with n (possibly multiple) edges.     

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.     

Planar segment visibility graphs

Given a set of n disjoint line segments in the plane, the segment visibility graph is the graph whose 2n vertices correspond to the endpoints of the line segments and whose edges connect every pair of vertices whose corresponding endpoints can see each other. In this paper we characterize and provide a polynomial time recognition algorithm for planar segment visibility graphs. Actually, we characterize segment visibility graphs that do not contain the complete graph K₅ as a minor, and show that this class is the same as the class of planar segment visibility graphs. We use and prove the fact that every segment visibility graph contains K₄ as a subgraph. In fact, we prove a stronger result: every set of n line segments determines at least n−3 empty convex quadrilaterals.     

Unavoidable doubly connected large graphs

A connected graph is doubly connected if its complement is also connected. The following Ramsey-type theorem is proved in this paper. There exists a function h(n), defined on the set of integers exceeding three, such that every doubly connected graph on at least h(n) vertices must contain, as an induced subgraph, a doubly connected graph, which is either one of the following graphs or the complement of one of the following graphs:

(1) P_n, a path on n vertices;

(2) K_1,n^s, the graph obtained from K_1,n by subdividing an edge once;

(3) K_2,ne, the graph obtained from K_2,n by deleting an edge;

(4) K_2,n⁺, the graph obtained from K_2,n by adding an edge between the two degree-n vertices x₁ and x₂, and a pendent edge at each x_i.

Two applications of this result are also discussed in the paper.     

Coloring permutation graphs in parallel

A coloring of a graph G is an assignment of colors to its vertices so that no two adjacent vertices have the same color. We study the problem of coloring permutation graphs using certain properties of the lattice representation of a permutation and relationships between permutations, directed acyclic graphs and rooted trees having specific key properties. We propose an efficient parallel algorithm which colors an n-node permutation graph in O(log² n) time using O(n²/log n) processors on the CREW PRAM model. Specifically, given a permutation π we construct a tree T^*[π], which we call coloring-permutation tree, using certain combinatorial properties of π. We show that the problem of coloring a permutation graph is equivalent to finding vertex levels in the coloring-permutation tree.     

The distance spectrum of the path Pn and The First Distance Eigenvector of Connected Graphs

Forumulas are given for all of the eigenvalues and eigenvectors of the distance matrix of the path P_n on n vertices. It is shown that P_n has the maximum distance spectral radius among all connected graphs of order n, and an ordering property of the entries of the Perron-Frobenius eigenvector is presented.