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 238

Showing per page

2-factors in claw-free graphs with locally disconnected vertices

Mingqiang An, Liming Xiong, Runli Tian (2015)

Czechoslovak Mathematical Journal

An edge of G is singular if it does not lie on any triangle of G ; otherwise, it is non-singular. A vertex u of a graph G is called locally connected if the induced subgraph G [ N ( u ) ] by its neighborhood is connected; otherwise, it is called locally disconnected. In this paper, we prove that if a connected claw-free graph G of order at least three satisfies the following two conditions: (i) for each locally disconnected vertex v of degree at least 3 in G , there is a nonnegative integer s such that v lies...

A conjecture on the prevalence of cubic bridge graphs

Jerzy A. Filar, Michael Haythorpe, Giang T. Nguyen (2010)

Discussiones Mathematicae Graph Theory

Almost all d-regular graphs are Hamiltonian, for d ≥ 3 [8]. In this note we conjecture that in a similar, yet somewhat different, sense almost all cubic non-Hamiltonian graphs are bridge graphs, and present supporting empirical results for this prevalence of the latter among all connected cubic non-Hamiltonian graphs.

A Fan-Type Heavy Pair Of Subgraphs For Pancyclicity Of 2-Connected Graphs

Wojciech Wideł (2016)

Discussiones Mathematicae Graph Theory

Let G be a graph on n vertices and let H be a given graph. We say that G is pancyclic, if it contains cycles of all lengths from 3 up to n, and that it is H-f1-heavy, if for every induced subgraph K of G isomorphic to H and every two vertices u, v ∈ V (K), dK(u, v) = 2 implies [...] min⁡dG(u),dG(v)≥n+12 min { d G ( u ) , d G ( v ) } ≥ n + 1 2 . In this paper we prove that every 2-connected K1,3, P5-f1-heavy graph is pancyclic. This result completes the answer to the problem of finding f1-heavy pairs of subgraphs implying pancyclicity...

A New Proof that 4-Connected Planar Graphs are Hamiltonian-Connected

Xiaoyun Lu, Douglas B. West (2016)

Discussiones Mathematicae Graph Theory

We prove a theorem guaranteeing special paths of faces in 2-connected plane graphs. As a corollary, we obtain a new proof of Thomassen’s theorem that every 4-connected planar graph is Hamiltonian-connected.

A note on a new condition implying pancyclism

Evelyne Flandrin, Hao Li, Antoni Marczyk, Mariusz Woźniak (2001)

Discussiones Mathematicae Graph Theory

We first show that if a 2-connected graph G of order n is such that for each two vertices u and v such that δ = d(u) and d(v) < n/2 the edge uv belongs to E(G), then G is hamiltonian. Next, by using this result, we prove that a graph G satysfying the above condition is either pancyclic or isomorphic to K n / 2 , n / 2 .

A Note on Barnette’s Conjecture

Jochen Harant (2013)

Discussiones Mathematicae Graph Theory

Barnette conjectured that each planar, bipartite, cubic, and 3-connected graph is hamiltonian. We prove that this conjecture is equivalent to the statement that there is a constant c > 0 such that each graph G of this class contains a path on at least c|V (G)| vertices.

A note on maximal common subgraphs of the Dirac's family of graphs

Jozef Bucko, Peter Mihók, Jean-François Saclé, Mariusz Woźniak (2005)

Discussiones Mathematicae Graph Theory

Let ⁿ be a given set of unlabeled simple graphs of order n. A maximal common subgraph of the graphs of the set ⁿ is a common subgraph F of order n of each member of ⁿ, that is not properly contained in any larger common subgraph of each member of ⁿ. By well-known Dirac’s Theorem, the Dirac’s family ⁿ of the graphs of order n and minimum degree δ ≥ [n/2] has a maximal common subgraph containing Cₙ. In this note we study the problem of determining all maximal common subgraphs of the Dirac’s family...

A note on the Song-Zhang theorem for Hamiltonian graphs

Kewen Zhao, Ronald J. Gould (2010)

Colloquium Mathematicae

An independent set S of a graph G is said to be essential if S has a pair of vertices that are distance two apart in G. In 1994, Song and Zhang proved that if for each independent set S of cardinality k+1, one of the following condition holds: (i) there exist u ≠ v ∈ S such that d(u) + d(v) ≥ n or |N(u) ∩ N(v)| ≥ α (G); (ii) for any distinct u and v in S, |N(u) ∪ N(v)| ≥ n - max{d(x): x ∈ S}, then G is Hamiltonian. We prove that if for each essential...

A Note on the Total Detection Numbers of Cycles

Henry E. Escuadro, Futaba Fujie, Chad E. Musick (2015)

Discussiones Mathematicae Graph Theory

Let G be a connected graph of size at least 2 and c :E(G)→{0, 1, . . . , k− 1} an edge coloring (or labeling) of G using k labels, where adjacent edges may be assigned the same label. For each vertex v of G, the color code of v with respect to c is the k-vector code(v) = (a0, a1, . . . , ak−1), where ai is the number of edges incident with v that are labeled i for 0 ≤ i ≤ k − 1. The labeling c is called a detectable labeling if distinct vertices in G have distinct color codes. The value val(c) of...

Currently displaying 1 – 20 of 238

Page 1 Next