Results 41 to 50 of about 413 (64)
The Hamiltonian index of a graph and its branch-bonds [PDF]
, 2001 Let $G$ be an undirected and loopless finite graph that is not a path. The minimum $m$ such that the iterated line graph $L^m(G)$ is hamiltonian is called the hamiltonian index of $G,$ denoted by $h(G).$ A reduction method to determine the hamiltonian ...
Broersma, Haitze J. +4 more
core +1 more source
Spectral Radius and Hamiltonicity of Graphs
Discussiones Mathematicae Graph Theory, 2019 In this paper, we study the Hamiltonicity of graphs with large minimum degree. Firstly, we present some conditions for a simple graph to be Hamilton-connected and traceable from every vertex in terms of the spectral radius of the graph or its complement,
Yu Guidong +3 more
doaj +1 more source
, 1996 The concept of a line digraph is generalized to that of a directed path graph. The directed path graph $\overrightarrow P_k(D)$ of a digraph D is obtained by representing the directed paths on k vertices of D by vertices.
Broersma, Hajo, Li, Xueliang
core +1 more source
Forbidden Pairs and (k,m)-Pancyclicity
Discussiones Mathematicae Graph Theory, 2017 A graph G on n vertices is said to be (k, m)-pancyclic if every set of k vertices in G is contained in a cycle of length r for each r ∈ {m, m+1, . . . , n}.
Crane Charles Brian
doaj +1 more source
, 2015 We suggest a measure of "Eulerianness" of a finite directed graph and define a class of "coEulerian" graphs. These are the graphs whose Laplacian lattice is as large as possible.
Farrell, Matthew, Levine, Lionel
core +1 more source
Dirac type condition and Hamiltonian graphs [PDF]
, 2011 2010 Mathematics Subject Classification: 05C38, 05C45.In 1952, Dirac introduced the degree type condition and proved that if G is a connected graph of order n і 3 such that its minimum degree satisfies d(G) і n/2, then G is Hamiltonian.
Zhao, Kewen
core
Spectral radius and traceability of connected claw-free graphs
, 2015 Let $G$ be a connected claw-free graph on $n$ vertices and $\overline{G}$ be its complement graph. Let $\mu(G)$ be the spectral radius of $G$. Denote by $N_{n-3,3}$ the graph consisting of $K_{n-3}$ and three disjoint pendent edges. In this note we prove
Li, Binlong, Ning, Bo
core +1 more source
On factors of 4-connected claw-free graphs [PDF]
, 1999 We consider the existence of several different kinds of factors in 4-connected claw-free graphs. This is motivated by the following two conjectures which are in fact equivalent by a recent result of the third author.
Broersma, H.J. +2 more
core +3 more sources
Heavy Subgraphs, Stability and Hamiltonicity
Discussiones Mathematicae Graph Theory, 2017 Let G be a graph. Adopting the terminology of Broersma et al. and Čada, respectively, we say that G is 2-heavy if every induced claw (K1,3) of G contains two end-vertices each one has degree at least |V (G)|/2; and G is o-heavy if every induced claw of G
Li Binlong, Ning Bo
doaj +1 more source
Chip-firing games on Eulerian digraphs and NP-hardness of computing the rank of a divisor on a graph
, 2015 Baker and Norine introduced a graph-theoretic analogue of the Riemann-Roch theory. A central notion in this theory is the rank of a divisor. In this paper we prove that computing the rank of a divisor on a graph is NP-hard.
Kiss, Viktor, Tóthmérész, Lilla
core +1 more source