Multigraphic Degree Sequences and Hamiltonian-connected Line Graphs  

作　　者：Ren-sen MA Ai-mei YU Ke-ke WANG Hong-Jian LAI 

机构地区：[1]Department of Mathematics,Beijing Jiaotong University,Beijing,100044,China [2]Department of Mathematics,Embry-Riddle Aeronautical University,Prescott,AZ,USA [3]Department of Mathematics,West Virginia University,Morgantown,WV,USA

出　　处：《Acta Mathematicae Applicatae Sinica》2021年第4期800-806,共7页应用数学学报（英文版）

基　　金：This paper is supported by the National Natural Science Foundation of China(Nos.11771039,11971054);Fundamental Research Funds for the Central Universities of China(No.2015JBM107);the 111 Project of China(No.B16002)。

摘　　要：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.

关 键 词：strongly spanning trailable graphs multigraphic degree sequence hamiltonian-connected graphs line graph 

分 类 号：O157.5[理学—数学]