Abstract | ||
---|---|---|
Dirac proved that if each vertex of a graph G of order n ⩾3 has degree at least n /2, then the graph is Hamiltonian. This result will be generalized by showing that if the union of the neighborhoods of each pair of vertices of a 2-connected graph G of sufficiently large order n has at least n /2 vertices, then G is Hamiltonian. Other results that are based on neighborhood unions of pairs of vertices will be proved that give the existence of cycles, paths and matchings. Also, Hamiltonian results will be considered that use the union of neighborhoods of more than 2 vertices. |
Year | DOI | Venue |
---|---|---|
1992 | 10.1016/0012-365X(92)90132-Y | Discrete Mathematics |
Keywords | Field | DocType |
neighborhood union,graph matching,hamiltonian graph,cycle graph | Discrete mathematics,Complete graph,Wheel graph,Combinatorics,Graph power,k-vertex-connected graph,Quartic graph,Cycle graph,Neighbourhood (graph theory),Mathematics,Path graph | Journal |
Volume | Issue | ISSN |
105 | 1-3 | Discrete Mathematics |
Citations | PageRank | References |
7 | 1.29 | 7 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
R. J. Faudree | 1 | 174 | 38.15 |
R. J. Gould | 2 | 23 | 4.92 |
M. S. Jacobson | 3 | 198 | 40.79 |
L. M. Lesniak | 4 | 44 | 8.23 |