摘要
设G是一个E(G)非空的图。图G的Gallai图Gal(G)是把G的边集作为它的点集,若G中的两条边e和f相邻但不在同一个三角形中,则Gal(G)中的两个不同顶点e和f相邻。显然,图G的Gallai图Gal(G)是线图L(G)的一个生成子图。本文刻画Gallai图分别是圈和完全k-部图的原图。
Let G be a graph with E(G)≠.The Gallai graph Gal(G) of a graph G has the edges of G as its vertices,and two distinct vertices e and f of Gal(G) are adjacent in Gal(G) if the edges e and f of G are adjacent in G but do not span a triangle in G.Clearly,the Gallai graph Gal(G) is a spanning subgraph of the well-known line graph L(G) of G.In this paper,we characterize those graphs whose Gallai graphs are cycles and complete k-partite graphs,respectively.
作者
郝琛
谢轶康
薛男
杨卫华
HAO Chen;XIE Yi-kang;XUE Nan;YANG Wei-hua(School of Electric Information Engineering,Jinzhong Vocational & Technical College,Jinzhong 030600,China;Department of Mathematics,Taiyuan University of Technology,Taiyuan 030024,China)
出处
《湖南师范大学自然科学学报》
CAS
北大核心
2019年第4期77-82,共6页
Journal of Natural Science of Hunan Normal University
基金
国家自然科学基金资助项目(11671296)
关键词
Gallai图
线图
完全k-部图
线图的生成子图
Gallai graph
line graph
complete k-partite graph
spanning subgraph of line graph