All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Page 1 Next

Displaying 1 – 20 of 24

Showing per page

Pairs Of Edges As Chords And As Cut-Edges

Terry A. McKee (2014)

Discussiones Mathematicae Graph Theory

Several authors have studied the graphs for which every edge is a chord of a cycle; among 2-connected graphs, one characterization is that the deletion of one vertex never creates a cut-edge. Two new results: among 3-connected graphs with minimum degree at least 4, every two adjacent edges are chords of a common cycle if and only if deleting two vertices never creates two adjacent cut-edges; among 4-connected graphs, every two edges are always chords of a common cycle.

Pairs of forbidden class of subgraphs concerning K 1 , 3 and P₆ to have a cycle containing specified vertices

Takeshi Sugiyama, Masao Tsugaki (2009)

Discussiones Mathematicae Graph Theory

In [3], Faudree and Gould showed that if a 2-connected graph contains no K 1 , 3 and P₆ as an induced subgraph, then the graph is hamiltonian. In this paper, we consider the extension of this result to cycles passing through specified vertices. We define the families of graphs which are extension of the forbidden pair K 1 , 3 and P₆, and prove that the forbidden families implies the existence of cycles passing through specified vertices.

Pancyclicity when each Cycle Must Pass Exactly k Hamilton Cycle Chords

Fatima Affif Chaouche, Carrie G. Rutherford, Robin W. Whitty (2015)

Discussiones Mathematicae Graph Theory

It is known that Θ(log n) chords must be added to an n-cycle to produce a pancyclic graph; for vertex pancyclicity, where every vertex belongs to a cycle of every length, Θ(n) chords are required. A possibly ‘intermediate’ variation is the following: given k, 1 ≤ k ≤ n, how many chords must be added to ensure that there exist cycles of every possible length each of which passes exactly k chords? For fixed k, we establish a lower bound of ∩(n1/k) on the growth rate.

Pancyclism and small cycles in graphs

Ralph Faudree, Odile Favaron, Evelyne Flandrin, Hao Li (1996)

Discussiones Mathematicae Graph Theory

We first show that if a graph G of order n contains a hamiltonian path connecting two nonadjacent vertices u and v such that d(u)+d(v) ≥ n, then G is pancyclic. By using this result, we prove that if G is hamiltonian with order n ≥ 20 and if G has two nonadjacent vertices u and v such that d(u)+d(v) ≥ n+z, where z = 0 when n is odd and z = 1 otherwise, then G contains a cycle of length m for each 3 ≤ m ≤ max (dC(u,v)+1, [(n+19)/13]), d C ( u , v ) being the distance of u and v on a hamiltonian cycle of G.

Path and cycle factors of cubic bipartite graphs

M. Kano, Changwoo Lee, Kazuhiro Suzuki (2008)

Discussiones Mathematicae Graph Theory

For a set S of connected graphs, a spanning subgraph F of a graph is called an S-factor if every component of F is isomorphic to a member of S. It was recently shown that every 2-connected cubic graph has a {Cₙ | n ≥ 4}-factor and a {Pₙ | n ≥ 6}-factor, where Cₙ and Pₙ denote the cycle and the path of order n, respectively (Kawarabayashi et al., J. Graph Theory, Vol. 39 (2002) 188-193). In this paper, we show that every connected cubic bipartite graph has a {Cₙ | n ≥ 6}-factor, and has a {Pₙ | n...

Path-Neighborhood Graphs

R.C. Laskar, Henry Martyn Mulder (2013)

Discussiones Mathematicae Graph Theory

A path-neighborhood graph is a connected graph in which every neighborhood induces a path. In the main results the 3-sun-free path-neighborhood graphs are characterized. The 3-sun is obtained from a 6-cycle by adding three chords between the three pairs of vertices at distance 2. A Pk-graph is a path-neighborhood graph in which every neighborhood is a Pk, where Pk is the path on k vertices. The Pk-graphs are characterized for k ≤ 4.

Paths of low weight in planar graphs

Igor Fabrici, Jochen Harant, Stanislav Jendrol' (2008)

Discussiones Mathematicae Graph Theory

The existence of paths of low degree sum of their vertices in planar graphs is investigated. The main results of the paper are: 1. Every 3-connected simple planar graph G that contains a k-path, a path on k vertices, also contains a k-path P such that for its weight (the sum of degrees of its vertices) in G it holds w G ( P ) : = ∑ u ∈ V ( P ) d e g G ( u ) ≤ ( 3 / 2 ) k ² + ( k ) 2. Every plane triangulation T that contains a k-path also contains a k-path P such that for its weight in T it holds w T ( P ) : = ∑ u ∈ V ( P ) d e g T ( u ) ≤ k ² + 13 k 3. Let G be a 3-connected simple planar graph of circumference...

Paths through fixed vertices in edge-colored graphs

W. S. Chou, Y. Manoussakis, O. Megalakaki, M. Spyratos, Zs. Tuza (1994)

Mathématiques et Sciences Humaines

We study the problem of finding an alternating path having given endpoints and passing through a given set of vertices in edge-colored graphs (a path is alternating if any two consecutive edges are in different colors). In particular, we show that this problem in NP-complete for 2-edge-colored graphs. Then we give a polynomial characterization when we restrict ourselves to 2-edge-colored complete graphs. We also investigate on (s,t)-paths through fixed vertices, i.e. paths of length s+t such that...

Paths with restricted degrees of their vertices in planar graphs

Stanislav Jendroľ (1999)

Czechoslovak Mathematical Journal

In this paper it is proved that every 3 -connected planar graph contains a path on 3 vertices each of which is of degree at most 15 and a path on 4 vertices each of which has degree at most 23 . Analogous results are stated for 3 -connected planar graphs of minimum degree 4 and 5 . Moreover, for every pair of integers n ≥ 3 , k ≥ 4 there is a 2 -connected planar graph such that every path on n vertices in it has a vertex of degree k .

Currently displaying 1 – 20 of 24

Page 1 Next