Let G(k) denote the set of connected k-regular graphs G, k≥2, where the number of vertices at distance 2 from any vertex in G does not exceed k. Asratian (2006) showed (using other terminology) that a graph G∈G(k) is Hamiltonian if for each vertex u of G the subgraph induced by the set of vertices at distance at most 2 from u is 2-connected. We prove here that in fact all graphs in the sets G(3), G(4) and G(5) are Hamiltonian. We also prove that the problem of determining whether there exists a Hamilton cycle in a graph from G(6) is NP-complete. Nevertheless we show that every locally connected graph G∈G(k), k≥6, is Hamiltonian and that for each non-Hamiltonian cycle C in G there exists a cycle C′ of length |V(C)|+ℓ in G, ℓ∈{1,2}, such that V(C)⊂V(C′). Finally, we note that all our conditions for Hamiltonicity apply to infinitely many graphs with large diameters.

A star edge coloring of a graph is a proper edge coloring with no 2-colored path or cycle of length four. The star chromatic index χst′(G) of G is the minimum number t for which G has a star edge coloring with t colors. We prove upper bounds for the star chromatic index of bipartite graphs G where all vertices in one part have maximum degree 2 and all vertices in the other part has maximum degree b. Let k be an integer (k≥1); we prove that if b=2k+1, then χst′(G)≤3k+2; and if b=2k, then χst′(G)≤3k; both upper bounds are sharp. We also consider complete bipartite graphs; in particular we determine the star chromatic index of such graphs when one part has size at most 3, and prove upper bounds for the general case. Finally, we consider the well-known conjecture that subcubic graphs have star chromatic index at most 6; in particular we settle this conjecture for cubic Halin graphs.