# Search Results

## You are looking at 1 - 4 of 4 items for :

• "Primary 05C38"
• Refine by Access: All Content
Clear All

# Estimations for the number of cycles in a graph

Periodica Mathematica Hungarica
Author: Lutz Volkmann
Restricted access

# Path extendable graphs

Periodica Mathematica Hungarica
Author: G. Hendry

## Abstract

A pathP in a graphG is said to beextendable if there exists a pathP’ inG with the same endvertices asP such thatV(P)⊆V (P’) and |V(P’)|=|V(P)|+1. A graphG ispath extendable if every nonhamiltonian path inG is extendable. We investigate the extent to which known sufficient conditions for a graph to be hamiltonian-connected imply the extendability of paths in the graph. Several theorems are proved: for example, it is shown that ifG is a graph of orderp in which the degree sum of each pair of non-adjacent vertices is at leastp+1 andP is a nonextendable path of orderk inG thenk≤(p+1)/2 and 〈V (P)〉≅K k orK ke. As corollaries of this we deduce that if δ(G)≥(p+2)/2 or if the degree sum of each pair of nonadjacent vertices inG is at least (3p−3)/2 thenG is path extendable, which strengthen results of Williamson .

Restricted access

# On translations of double rays in graphs

Periodica Mathematica Hungarica
Authors: Norbert Polat and Mark E. Watkins

Let t be an infinite graph, let p be a double ray in t, and letd anddp denote the distance functions in t and in p, respectively. One calls p anaxis ifd(x,y)=d p (x,y) and aquasi-axis if lim infd(x,y)/d p (x,y)>0 asx, y range over the vertex set of p andd p (x,y)?8. The present paper brings together in greater generality results of R. Halin concerning invariance of double rays under the action of translations (i.e., graph automorphisms all of whose vertex-orbits are infinite) and results of M. E. Watkins concerning existence of axes in locally finite graphs. It is shown that if a is a translation whose directionD(a) is a thin end, then there exists an axis inD(a) andD(a-1) invariant under ar for somer not exceeding the maximum number of disjoint rays inD(a).The thinness ofD(a) is necessary. Further results give necessary conditions and sufficient conditions for a translation to leave invariant a quasi-axis.

Restricted access

# Graphs with prescribed degree sets and girth

Periodica Mathematica Hungarica
Authors: G. Chartrand, R. Gould, and S. Kapoor
Restricted access