✦ LIBER ✦

Longest paths and cycles in bipartite oriented graphs

✍ Scribed by Zhang Ke Min

Publisher: John Wiley and Sons
Year: 1987
Tongue: English
Weight: 430 KB
Volume: 11
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190110308

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper we obtain two sufficient conditions, Ore type (Theorem 1) and Dirac type (Theorem 2). on the degrees of a bipartite oriented graph for ensuring the existence of long paths and cycles. These conditions are shown to be the best possible in a sense.

An oriented graph is a digraph without loops, multiple arcs, or cycles of length two. We will refer to an oriented complete bipartite graph as a bipartite tournament. Let R = ( V ( R ) , A @ ) ) be a bipartite oriented graph, where V ( R ) and A ( R ) denote the set of vertices and the set of arcs of R , respectively. For u E V(R) and B C V(R), define N,(u) and N,'(u) to be the set of vertices of B , which dominate, and are dominated by, the vertex u , respectively. Put

NB(u) = N,(u) U N ~( u ) .

We shall refer to N;(u) = INa(u)l, dd(u) = INd(u)I and dB(u) = INB(u)I as the in-degree, the out-degree, and the degree of u in B , for any u E V(R), and m-diconnected if, for any distinct pair of vertices u , u E V ( R ) , there exist m internally disjoint paths from u to u . If R is 1disconnected, we shall say simply that R is disconnected. We follow [2] for other terminology and notation.

The longest directed paths and cycles in oriented graph were discussed in [ 1,3,41. In this paper we obtained further results on this problem. We shall prove several Lemmas before proving our main results.

📜 SIMILAR VOLUMES

Longest paths and cycles in K1,3-free gr

Longest paths and cycles in K1,3-free graphs

✍ Manton M. Matthews; David P. Sumner 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 383 KB 👁 2 views

In this article w e show that the standard results concerning longest paths and cycles in graphs can be improved for K,,,-free graphs. We obtain as a consequence of these results conditions for the existence of a hamiltonian path and cycle in K,,,-free graphs.

Relative length of longest paths and cyc

Relative length of longest paths and cycles in 3-connected graphs

✍ Rao Li; Akira Saito; R.H. Schelp 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 184 KB 👁 2 views

## Abstract For a graph __G__, let __p(G)__ denote the order of a longest path in __G__ and __c(G)__ the order of a longest cycle in __G__, respectively. We show that if __G__ is a 3‐connected graph of order __n__ such that $\textstyle{\sum^{4}\_{i=1}\,{\rm deg}\_{G}\,x\_{i} \ge {3\over2}\,n + 1}$

Longest cycles in tough graphs

✍ Jung, H.A.; Wittmann, P. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 347 KB 👁 2 views

In this article, we establish bounds for the length of a longest cycle C in a 2-connected graph G in terms of the minimum degree δ and the toughness t. It is shown that C is a Hamiltonian cycle or |C| ≥ (t + 1)δ + t.

Intersections of longest cycles in grid

Intersections of longest cycles in grid graphs

✍ Menke, B.; Zamfirescu, T.; Zamfirescu, C. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 292 KB 👁 3 views

It is well-known that the largest cycles of a graph may have empty intersection. This is the case, for example, for any hypohamiltonian graph. In the literature, several important classes of graphs have been shown to contain examples with the above property. This paper investigates a (nontrivial) cl

Chords of Longest Cycles in Cubic Graphs

✍ Carsten Thomassen 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 213 KB

We describe a general sufficient condition for a Hamiltonian graph to contain another Hamiltonian cycle. We apply it to prove that every longest cycle in a 3-connected cubic graph has a chord. We also verify special cases of an old conjecture of Sheehan on Hamiltonian cycles in 4-regular graphs and

On relative length of longest paths and

On relative length of longest paths and cycles

✍ Kenta Ozeki; Masao Tsugaki; Tomoki Yamashita 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 144 KB 👁 1 views

## Abstract For a graph __G__, __p__(__G__) and __c__(__G__) denote the order of a longest path and a longest cycle of __G__, respectively. In this paper, we prove that if __G__ is a 3 ‐connected graph of order __n__ such that the minimum degree sum of four independent vertices is at least __n__+ 6