华东师范大学学报（自然科学版） >

2018 , Vol. 2018 >Issue 2: 23 - 30,40

DOI: https://doi.org/10.3969/j.issn.1000-5641.2018.02.003

数学

探索Euler图的等价命题

  • 孙慧 ,
  • 姚兵
展开
  • 1. 西北师范大学 数学与统计学院, 兰州 730070;
    2. 兰州交通大学 电子与信息工程学院, 兰州 730070
孙慧,女,硕士研究生,研究方向为图着色与标号、复杂网络.E-mail:18919104606@163.com.

收稿日期: 2017-02-20

  网络出版日期: 2018-03-22

基金资助

国家自然科学基金（61163054，61363060，61662066）

收起

Exploring equivalent definitions of eulerian graphs

  • SUN Hui ,
  • YAO Bing
Expand
  • 1. College of Mathematics and Statistics, Northwest Normal University, Lanzhou 730070, China;
    2. School of Electronic and Information Engineering, Lanzhou Jiaotong University, Lanzhou 730070, China

Received date: 2017-02-20

  Online published: 2018-03-22

Fold

摘要

从研究Euler图的等价命题入手，尝试挖掘Euler图的拓扑结构，力图从多个角度刻画Euler图的本征，得到4个新的Euler图等价命题，并利用图的"浓缩"和"稀释"运算给出刻画Euler图的技术，且此技术能够转化为可行的算法.

关键词： Euler图; 无邻顶点重合运算; 边收缩运算; 顶点剖分运算; 2-度拆分运算

本文引用格式

孙慧 , 姚兵 . 探索Euler图的等价命题[J]. 华东师范大学学报（自然科学版）, 2018 , 2018(2) : 23 -30,40 . DOI: 10.3969/j.issn.1000-5641.2018.02.003

Abstract

From the topic of equivalent propositions of eulerian graph to start our study, we try to dig the topology of eulerian graph, and to describe eulerian graph from the view of different insights. Finally, we obtain four new equivalent propositions of eulerian graph by the technique of "concentration" and "dilution" operations, which can be transformed into two feasible algorithms.

Key words： eulerian graph; non-adjacent identifying operation; edge contraction operation; vertex subdivision operation; 2-degree split operation

参考文献

[1] BONDY A J, MURTY U S R. Graph Theory with Applications[M]. London:The MaCmillan Press Ltd, 1976.
[2] 石怡, 王旭培. 欧拉图的最大特征值[J]. 湖州师范学院学报, 2008, 30(2):13-15.
[3] 侯远, 陈育栎, 郑艺容, 等. 欧拉图的hyper-Wiener指标[J]. 高校应用数学学报, 2016, 31(2):248-252.
[4] CHEN Z H. Snarks, hypohamiltonian graphs and non-supereulerian graphs[J]. Graphs and Combinatorics, 2016, 32(6):2267-2273.
[5] 李赤松, 李战春, 江敏. 基于欧拉图的授权扩散拓扑构建与授权撤销[J]. 小型微型计算机系统, 2012, 33(10):2208-2212.
[6] 游松发, 赵红艳. 欧拉图与Capelli多项式[J]. 湖北大学学报(自然科学版), 2011, 33(4):444-447.
[7] 赵红艳. 欧拉图与矩阵环的多项式恒等式[D]. 武汉:湖北大学, 2013.
[8] 唐海宏. 欧拉图在逻辑教学中的运用[J]. 林区教学,, 2012(10):4-5.
[9] SUO X, ZHU Y, OWEN G S. Graphical passwords:A survey[C]//Computer Security Applications Conference. DBLP, 2005:463-472.
[10] FLEISCHNER H. 欧拉图与相关专题[M]. 孙志人, 李皓, 刘桂珍, 等, 译. 北京:科学出版社, 2012.
[11] 陈慧敏. 在Ck(l, m)中的k-超欧拉图[D]. 武汉:华中师范大学, 2015.
[12] 安明强, 熊黎明. 超欧拉图、可折叠图及匹配[J]. 应用数学学报, 2016, 39(6):871-877.
[13] WANG B. A degree-sum condition for edge-supereulerian graphs[J]. Journal of Southwest China Normal University, 2009, 34(1):16-19.
[14] 李登信, 王斌, 李宵民. 关于判定超欧拉图的收缩法[J]. 重庆工商大学学报(自然科学版), 2003, 20(1):1-4.
[15] 李霄民. 判定超欧拉图的一个新方法[J]. 西南大学学报(自然科学版), 2007, 29(4):41-43.
[16] 苏静, 马飞, 姚兵. 2-连通图的一些等价定义[J]. 东北师大学报(自然科学版), 2017, 49(1):33-37.
[17] 苏静, 马飞, 姚兵. 探索2-边连通图的等价定义[J]. 华东师范大学学报(自然科学版), 2017(1):19-25.
[18] 王晓敏, 赵喜杨, 姚兵. 关于树的若干等价性命题[J]. 陕西师范大学学报(自然科学版), 2016, 44(2):11-14.
Options
文章导航

/

〈 〉