Ren-sen MA, Ai-mei YU, Ke-ke WANG, Hong-Jian LAI
Let G be a multigraph. Suppose that e=u1v1 and e'=u2v2 are two edges of G. If e ≠ e', then G(e, e') is the graph obtained from G by replacing e=u1v1 with a path u1vev1 and by replacing e'=u2v2 with a path u2ve'v2, where ve, ve' are two new vertices not in V(G). If e = e', then G(e, e'), also denoted by G(e), is obtained from G by replacing e=u1v1 with a path u1vev1. A graph G is strongly spanning trailable if for any e, e' ∈ E(G), G(e, e') has a spanning (ve, ve')-trail.
The design of n processor network with given number of connections from each processor and with a desirable strength of the network can be modelled as a degree sequence realization problem with certain desirable graphical properties. A sequence d=(d1, d2, ..., dn) is multigraphic if there is a multigraph G with degree sequence d, and such a graph G is called a realization of d. A multigraphic degree sequence d is strongly spanning trailable if d has a realization G which is a strongly spanning trailable graph, and d is line-hamiltonian-connected if d has a realization G such that the line graph of G is hamiltonian-connected. In this paper, we prove that a nonincreasing multigraphic sequence d=(d1, d2, ..., dn) is strongly spanning trailable if and only if either n=1 and d1=0 or n ≥ 2 and dn ≥ 3. Applying this result, we prove that for a nonincreasing multigraphic sequence d=(d1, d2, ..., dn), if n ≥ 2 and dn ≥ 3, then d is line-hamiltonian-connected.
