[1]崔秋月,刘 娟*,董畅畅.超欧拉和双有向迹的强积有向图[J].四川师范大学学报(自然科学版),2018,(04):489-494.[doi:10.3969/j.issn.1001-8395.2018.04.010]
 CUI Qiuyue,LIU Juan,DONG Changchang.Supereulerian and Bi-trailable Strong Product Digraphs[J].Journal of SichuanNormal University,2018,(04):489-494.[doi:10.3969/j.issn.1001-8395.2018.04.010]
点击复制

超欧拉和双有向迹的强积有向图()
分享到:

《四川师范大学学报(自然科学版)》[ISSN:1001-8395/CN:51-1295/N]

卷:
期数:
2018年04期
页码:
489-494
栏目:
基础理论
出版日期:
2018-04-15

文章信息/Info

Title:
Supereulerian and Bi-trailable Strong Product Digraphs
文章编号:
1001-8395(2018)04-0489-06
作者:
崔秋月 刘 娟* 董畅畅
新疆师范大学 数学科学学院, 新疆 乌鲁木齐 830017
Author(s):
CUI Qiuyue LIU Juan DONG Changchang
College of Mathematical Science, Xinjiang Normal University, Urumqi 830017, Xinjiang
关键词:
超欧拉有向图 双有向迹有向图 强积 欧拉有向图
Keywords:
super Eulerian digraph bi-trailable digraph strong product Eulerian digraph
分类号:
O157.6
DOI:
10.3969/j.issn.1001-8395.2018.04.010
文献标志码:
A
摘要:
如果D是简单有向图(无自环与平行弧)并且包含一个生成欧拉子有向图,则称D是超欧拉有向图.如果D中存在2个不同的点x,y,使得D既有生成(x,y)-有向迹又有生成(y,x)-有向迹,则称D是双有向迹有向图.主要研究了关于2个有向图D1和D2的强积有向图成为超欧拉有向图或双有向迹有向图的充分条件.
Abstract:
A simple digraph D(without loops and parallel arcs)is super Eulerian if D contains a spanning Eulerian subdigraph, D is bi-trailable if there exist two distinct vertices x,y ∈V(D), such that D has both spanning (x,y)-ditrail and spanning (y,x)-ditrail.In this paper, we obtain the sufficient conditions on the strong product digraph D1ⓧD2 to be super Eulerian digraph or bi-trailable digraph.

参考文献/References:

[1] BONDY J A, MURTY U S R.Graph Theory[M].New York:Springer-Verlag,2008.
[2] BANG-JENSEN J, GUTIN G.Digraphs:Theory Algorithms and Applications[M].2nd ed.New York:Springer-Verlag,2010.
[3] BOESCH F T, SUFFEL C, TINDELL R.The spanning subgraphs of Eulerian graphs[J].J Graph Theory,1977,1(1):79-84.
[4] PULLEYBLANK W R.A note on graphs spanned by Eulerian graphs[J].J Graph Theory,1979,3(3):309-310.
[5] CATLIN P A.Supereulerian graphs:a survey[J].J Graph Theory,1992,16(2):177-196.
[6] CHEN Z H, LAI H J.Reduction techniques for super-Eulerian graphs and related topics:a survey[C]//Combinatorics and Graph Theory.New Jersey:World Science Citation Index Publishing,1995:53-69.
[7] LAI H J, SHAO Y, YAN H.An update on supereulerian graphs[J].World Scientific and Engineering Academy Society Transactions on Mathematics,2013,12(9):926-940.
[8] GUTIN G.Cycles and paths in directed graphs[D].Tel Aviv:Tel Aviv University,1993.
[9] GUTIN G.Connected (g; f)-factors and supereulerian digraphs[J].Ars Combinatoria,2000,52:311-317.
[10] ALGEFARI M J, ALSATAMI K A, LAI H J, et al.Supereulerian digraphs with given local structures[J].Information Processing Letters,2016,116(5):321-326.
[11] BANG-JENSEN J, MADDALONI A.Sufficient conditions for a digraph to be supereulerian[J].J Graph Theory,2015,79(1):8-20.
[12] HONG Y, LAI H J, LIU Q.Supereulerian digraphs[J].Discrete Mathematics,2014,330:87-95.
[13] GOULD R J.Advances on the Hamiltonian problem:a survey[J].Graphs and Combinatorics,2003,19:7-52.
[14] DONG C, LIU J, ZHANG X, et al.Supereulerian digraphs with given diameter[J].Appl Math Comput,2018,329:5-13.
[15] ALSATAMI K A, ZHANG X D, LIU J, et al.On a class of supereulerian digraphs[J].Appl Math,2016,7(3):320-326.

备注/Memo

备注/Memo:
收稿日期:2016-11-14 接受日期:2017-04-13
基金项目:国家自然科学基金(11761071)
*通信作者简介:刘 娟(1981—),女,教授,主要从事图论及其应用的研究工作,E-mail:liujuan1999@126.com
更新日期/Last Update: 2018-04-15