您的位置：山东大学 -> 科技期刊社 -> 《山东大学学报（理学版）》

山东大学学报（理学版） ›› 2015, Vol. 50 ›› Issue (02): 38-42.doi: 10.6040/j.issn.1671-9352.0.2014.324

• 论文 • 上一篇    下一篇

嵌入曲面的图的点荫度

孙林1, 蔡华2   

  1. 1. 昌吉学院数学系, 新疆 昌吉 831100;
    2. 山东大学数学学院, 山东 济南 250100
  • 收稿日期:2014-07-15 修回日期:2014-10-21 出版日期:2015-02-20 发布日期:2015-01-27
  • 作者简介:孙林(1981-),女,博士研究生,讲师,研究方向为图论及复杂网络. E-mail:fiona_sl@163.com
  • 基金资助:
    新疆维吾尔自治区高等学校科研计划项目(XJEDU2014S067)

On the vertex-arboricity of embedded graphs

SUN Lin1, CAI Hua2   

  1. 1. Department of Mathematics, Changji University, Changji 831100, Xinjiang, China;
    2. School of Mathematics, Shandong University, Jinan 250100, Shandong, China
  • Received:2014-07-15 Revised:2014-10-21 Online:2015-02-20 Published:2015-01-27

PDF (PC)

578

摘要： 图G的导出森林k-划分是指其顶点集V(G)的一个k-划分(V1,V2,…,Vk),使得对于每个 i (1≤i≤k),导出子图G[Vi]是一个森林.图G的点荫度是使得图G有导出森林k-划分的最小的正整数k,记为va(G).主要证明了如果图G能够嵌入到欧拉示性数非负的曲面上,则当图G满足三类条件时,可以得到va(G)≤2.

关键词: 点荫度, 放电法, 距离

Abstract: An induced forest k-partition of a graph G is a k-partition (V1,V2,…,Vk) of the vertex set V(G) such that, for each i with 1≤i≤k, the induced subgraph G[Vi] is a forest. The vertex arboricity of a graph G is the minimum positive integer k such that G has an induced forest k-partition, denoted by va(G). Let G be a simple graph embedded in a surface of nonnegative Euler characteristic, and if G satisfies three kinds of conditions, then va(G)≤2.

Key words: discharging method, vertex arboricity, distance

中图分类号: 

  • O157.5
[1] BONDY J A, MURTY U S R. Graph theory with applications[M]. New York: North-Holland, 1976.
[2] CHARTRAND G, KRONK H V, WALL C E. The point-arboricity of a graph[J]. Discrete mathematics, 1968, 6:169-175.
[3] YANG Aifeng, YUAN Jinjiang. On the vertex-arboricity of planar graphs of diameter two[J]. Discrete Mathematics, 2007, 307:2438-2447.
[4] HUANG Danjun, SHIU Wai Chee, WANG Weifan. On the vertex-arboricity of planar graphs without 7-cycles[J]. Discrete Mathematics, 2012, 312:2304-2315.
[5] HUANG Danjun, WANG Weifan. Vertex-arboricity of planar graphs without chordal 6-cycles[J]. International Journal of Computer Mathematics, 2013, 90(2):258-272.
[6] CHEN Min, ANDRE Raspand, WANG Weifan. Vertex-arboricity of planar graphs without intersecting triangles[J]. European Journal of Combinatorics, 2012, 33:905-923.
[7] RASPAND A, WANG Weifan. On the vertex-arboricity of planar graphs[J]. European Journal of Combinatorics, 2008, 29:1064-1075.
[1] 徐伟呈,李欣鹏. 单边不完全信息重复博弈中的Cav(u)定理的推广[J]. 山东大学学报（理学版）, 2018, 53(4): 42-45.
[2] 李小娟,高强. 次线性期望框架下乘积空间的正则性[J]. 山东大学学报（理学版）, 2018, 53(4): 66-75.
[3] 黄栋,徐博,许侃,林鸿飞,杨志豪. 基于词向量和EMD距离的短文本聚类[J]. 山东大学学报（理学版）, 2017, 52(7): 66-72.
[4] 朱晓颖,逄世友. 控制数给定的树的最大离心距离和[J]. 山东大学学报（理学版）, 2017, 52(2): 30-36.
[5] 岳猛,吴志军,姜军. 云计算中基于可用带宽欧氏距离的LDoS攻击检测方法[J]. 山东大学学报（理学版）, 2016, 51(9): 92-100.
[6] 翟鹏,李登道. 基于高斯隶属度的包容性指标模糊聚类算法[J]. 山东大学学报（理学版）, 2016, 51(5): 102-105.
[7] 刘颖莹,刘培玉,王智昊,李情情,朱振方. 一种基于密度峰值发现的文本聚类算法[J]. 山东大学学报（理学版）, 2016, 51(1): 65-70.
[8] 桑乐园, 徐新峰, 张婧, 黄德根. 基于广义Jaccard系数的微博情感新词判定[J]. 山东大学学报（理学版）, 2015, 50(07): 71-75.
[9] 林宏康1,2,李豫颖1,2,熊国敏3. 动态数据距离与动态数据几何辨识-恢复[J]. J4, 2012, 47(8): 92-97.
[10] 黄林晟1,邓志鸿1,2,唐世渭1,2,王文清3,陈凌3. 基于编辑距离的中文组织机构名简称-全称匹配算法[J]. J4, 2012, 47(5): 43-48.
[11] 赵为华1, 冯予2, 李泽安3. 广义二项回归模型的影响诊断[J]. J4, 2011, 46(1): 97-103.
[12] 张雪凤1,刘鹏1,2. 基于类间差异最大化的加权距离改进K-means算法[J]. J4, 2010, 45(7): 28-33.
[13] 宋颖，张兴芳. £ukasiewicz n值命题逻辑中公式的α-随机真度理论[J]. J4, 2010, 45(5): 74-77.
[14] 马宝林1,2, 陈祥恩1*, 刘娟2. 图的强直积的2-距离染色[J]. J4, 2010, 45(3): 66-70.
[15] 崔美华. 逻辑系统G3中命题的D-条件真度与近似推理[J]. J4, 2010, 45(11): 52-58.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 2018 《山东大学学报(理学版)》编辑部　
地址: 山东省济南市山大南路27号山东大学中心校区（250100）　电话: +86-0531-88366917　E-mail: xblxb@sdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发