On 2-factors with cycles containing specified edges in a bipartite graph

Let k≥1 be an integer and G=(V₁,V₂;E) a bipartite graph with |V₁|=|V₂|=n such that n≥2k+2. In this paper it has been proved that if for each pair of nonadjacent vertices x∈V₁ and y∈V₂, , then for any k independent edges e₁,…,e_k of G, G has a 2-factor with k+1 cycles C₁,…,C_k+1 such that e_i∈E(C_i) and |V(C_i)|=4 for each i∈{1,…,k}. We shall also show that the conditions in this paper are sharp.     

Vertex‐disjoint cycles containing specified vertices in a bipartite graph

A minimum degree condition is given for a bipartite graph to contain a 2‐factor each component of which contains a previously specified vertex. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 145–166, 2004     

Circuits containing specified edges

Given any l(≥ 2) disjoint edges in a (2l ? 2)-connected graph, there is a circuit containing all of them.     

Note on circuits containing specified edges

If L is a set of at most l disjoint edges in a $\text{[}\text{3}\text{2}\text{l?}\text{1}\text{2}\text{]-}\text{connected}$ graph, then there is a circuit containing all edges of L.     

The number of edges in a bipartite graph of given radius

Vizing established an upper bound on the size of a graph of given order and radius. We find a sharp upper bound on the size of a bipartite graph of given order and radius.     

Vertex-disjoint chorded cycles in a graph

In this paper we prove: Let k≥1 be an integer and G be graph with at least 4k vertices and minimum degree at least ⌊7k/2⌋. Then G contains k vertex-disjoint cycles such that each of them has at least two chords in G.     

Convex hull of the edges of a graph and near bipartite graphs

First we characterize the convex hull of the edges of a graph, edges viewed as the characteristic function of the hereditary closure of some subset of the 2-elements set of a finite set X. This characterization becomes more simple for a class of graphs that we call near bipartite, NBP in short. This class is then characterized as the class of graphs such that ?x?X, G_X\r(x), the induced subgraph of the complementary of the neighbourhood of x, is bipartite. We made a partial study of this class, whose interest is justified by the constatation that the following classes are strictly include: $\text{L(G)}$ the edge complementary of the line graph of G. NBP, $\text{K}{}_{13}$-free graphs.     

Disjoint triangles and quadrilaterals in a graph

Let n, s and t be three integers with s ≥ 1, t ≥ 0 and n = 3s + 4t. Let G be a graph of order n such that the minimum degree of G is at least (n + s)/2. Then G contains a 2-factor with s + t components such that s of them are triangles and t of them are quadrilaterals.      

Disjoint directed quadrilaterals in a directed graph

Let D be a directed graph of order 4k, where k is a positive integer. Suppose that the minimum degree of D is at least 6k ? 2. We show that D contains k disjoint directed quadrilaterals with only one exception. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Disjoint triangles and quadrilaterals in a graph

Let G be a simple graph of order n and s and k be two positive integers. Brandt et al. obtained the following result: If s?k, n?3s+4(k-s) and σ₂(G)?n+s, then G contains k disjoint cycles C₁,…,C_k satisfying |C_i|=3 for 1?i?s and |C_i|?4 for s<i?k. In the above result, the length of C_i is not specified for s<i?k. We get a result specifying the length of C_i for each s<i?k if n?3s+4(k-s)+3.     

Even factor of bridgeless graphs containing two specified edges

An even factor of a graph is a spanning subgraph in which each vertex has a positive even degree. Let G be a bridgeless simple graph with minimum degree at least 3. Jackson and Yoshimoto (2007) showed that G has an even factor containing two arbitrary prescribed edges. They also proved that G has an even factor in which each component has order at least four. Moreover, Xiong, Lu and Han (2009) showed that for each pair of edges e₁ and e₂ of G, there is an even factor containing e₁ and e₂ in which each component containing neither e₁ nor e₂ has order at least four. In this paper we improve this result and prove that G has an even factor containing e₁ and e₂ such that each component has order at least four.     

A look at cycles containing specified elements of a graph

This article is intended as a brief survey of problems and results dealing with cycles containing specified elements of a graph. It is hoped that this will help researchers in the area to identify problems and areas of concentration.     

Diameter-vital edges in a graph

The graph resulting from contracting edge e is denoted as G/e and the graph resulting from deleting edge e is denoted as G − e. An edge e is diameter-essential if diam(G/e) < diam(G), diameter-increasing if diam(G − e) < diam(G), and diameter-vital if it is both diameter-essential and diameter-increasing. We partition the edges that are not diameter-vital into three categories. In this paper, we study realizability questions relating to the number of edges that are not diameter-vital in the three defined categories. A graph is diameter-vital if all its edges are diameter-vital. We give a structural characterization of diameter-vital graphs.     

Diameter-essential edges in a graph

The eccentricity e(v) of v is the distance to a farthest vertex from v. The diameter diam(G) is the maximum eccentricity among the vertices of G. The contraction of edge e=uv in G consists of removing e and identifying u and v as a single new vertex w, where w is adjacent to any vertex that at least one of u or v were adjacent to. The graph resulting from contracting edge e is denoted G/e. An edge e is diameter-essential if diam(G/e)<diam(G). Let c(G) denote the number of diameter-essential edges in graph G. In this paper, we study existence and extremal problems for c(G); determine bounds on c(G) in terms of diameter and order; and obtain characterizations of graphs achieving extreme values of c(G).     

Circuits through specified edges

We prove a theorem implying the conjecture of Woodall [14] that, given any k independent edges in a (k+1)-connected graph, there is a circuit containing all of them. This implies the truth of a conjecture of Berge [1, p.214] and provides strong evidence to a conjecture of Lovász [8].     

Non-contractible edges in a 3-connected graph

An edgee in a 3-connected graphG is contractible if the contraction ofe inG results in a 3-connected graph; otherwisee is non-contractible. In this paper, we prove that the number of non-contractible edges in a 3-connected graph of orderp≥5 is at most $$3p - \left[ {\frac{3}{2}(\sqrt {24p + 25} - 5} \right],$$ and show that this upper bound is the best possible for infinitely many values ofp.     

Partitioning the edges of a graph

For any integer m (≥2), it is known that there are simple graphs of maximum valence m whose edges cannot be coloured with m colours in such a way that adjacent edges shall have different colours. We find those values of m and k for which it is true that every simple graph whose maximum valence does not exceed mk can be coloured with m colours in such a way that no colour appears more than k times at any vertex.     

Biclosure and bistability in a balanced bipartite graph

The k-biclosure of a balanced bipartite graph wiht color classes A and B is the graph obtained from G by recursively joining pairs of nonadjacent vertices respectively taken in A and B whose degree sum is at least k, until no such pair remains. A property P defined on all the balanced bipartite graphs of order 2n is k-bistable if whenever G + ab has property P and d_G(b) ≧ k then G itself has property P. We present a synthesis of results involving, for some properties, P, the bistability of P, the k-biclosure of G, the number of edges and the minimum degree. © 1995 John Wiley & Sons, Inc.