Some cyclic properties of L₁-graphs

Publication date 15 April 2019

Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45)

Abstract: A graph

G

is called an

L_{1}

-graph if

d (u) + d (v) g e | N (u) c u p N (v) c u p N (w) | - 1

for every triple of vertices

u, v, w

where

u

and

v

are at distance 2 and

w i n N (u) c a p N (v)

. Asratian et al. (1996) proved that all finite connected

L_{1}

-graphs on at least three vertices such that

| N (u) c a p N (v) | g e 2

for each pair of vertices

u, v

at distance 2 are Hamiltonian, except for a simple family

m a t h c a l K

of exceptions. We show that not all such graphs are pancyclic, but that any non-Hamiltonian cycle in such a graph can be extended to a larger cycle containing all vertices of the original cycle and at most two other vertices. We also prove a similar result for paths whose endpoints do not have any common neighbors.

This page was built for publication: Some cyclic properties of $L_1$-graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6317225)