Large Degree Vertices in Longest Cycles of Graphs, I
In this paper, we consider the least integer d such that every longest cycle of a k-connected graph of order n (and of independent number α) contains all vertices of degree at least d.
In this paper, we consider the least integer d such that every longest cycle of a k-connected graph of order n (and of independent number α) contains all vertices of degree at least d.
Let be a path on vertices. In an earlier paper we have proved that each polyhedral map on any compact -manifold with Euler characteristic contains a path such that each vertex of this path has, in , degree . Moreover, this bound is attained for or , even. In this paper we prove that for each odd , this bound is the best possible on infinitely many compact -manifolds, but on infinitely many other compact -manifolds the upper bound can be lowered to .
A collection (1 ≤ t ≤ k) of t disjoint paths, s of them being singletons with |V(L)| = k is called a (k,t,s)-linear forest. A graph G is (k,t,s)-ordered if for every (k,t,s)-linear forest L in G there exists a cycle C in G that contains the paths of L in the designated order as subpaths. If the cycle is also a hamiltonian cycle, then G is said to be (k,t,s)-ordered hamiltonian. We give sharp sum of degree conditions for nonadjacent vertices that imply a graph is (k,t,s)-ordered hamiltonian.
It is shown that every 3-connected planar graph with a large number of vertices has a long induced path.
L-zero-divisor graphs of L-commutative rings have been introduced and studied in [5]. Here we consider L-zero-divisor graphs of a finite direct product of L-commutative rings. Specifically, we look at the preservation, or lack thereof, of the diameter and girth of the L-ziro-divisor graph of a L-ring when extending to a finite direct product of L-commutative rings.
A buttoning of a tree that has vertices v1, v2, . . . , vn is a closed walk that starts at v1 and travels along the shortest path in the tree to v2, and then along the shortest path to v3, and so forth, finishing with the shortest path from vn to v1. Inspired by a problem about buttoning a shirt inefficiently, we determine the maximum length of buttonings of trees