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.
Le problème du voyageur de commerce dans un produit cartésien de deux graphes
Light paths with an odd number of vertices in polyhedral maps
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 .
Linear forests and ordered cycles
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.
Locally graphs.
Locally path-like graphs
Locally snake-like graphs
Long cycles and neighborhood union in 1-tough graphs with large degree sums
Long cycles in certain graphs of large degree.
Long heterochromatic paths in edge-colored graphs.
Long induced paths in 3-connected planar graphs
It is shown that every 3-connected planar graph with a large number of vertices has a long induced path.
Longest cycles in certain bipartite graphs.
Longest induced cycles in circulant graphs.
Loop-erased random walks, spanning trees and Hamiltonian cycles.
Loose Hamilton cycles in random uniform hypergraphs.
L-zero-divisor graphs of direct products of L-commutative rings
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.
Maximal buttonings of trees
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
Maximal nontraceable graphs with toughness less than one.
Maximal pentagonal packings.
Maximum cardinality 1-restricted simple 2-matchings.