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

山东大学学报（理学版） ›› 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)

804

摘要： 图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] 申云瑞,梅银珍. 运算图的电阻距离和基尔霍夫指数[J]. 《山东大学学报(理学版)》, 2026, 61(4): 92-101.
[2] 李季,刘艾汶,秦柳. 基于非零水平集保凸算法的左心室MRI分割[J]. 《山东大学学报(理学版)》, 2025, 60(7): 32-47.
[3] 陈旭,邵荣侠,王国平. 带有割点的图的补图的距离谱半径[J]. 《山东大学学报(理学版)》, 2025, 60(2): 19-23.
[4] 田双亮,陈萍. 路的半强积与强积的距离染色[J]. 《山东大学学报(理学版)》, 2025, 60(12): 167-172.
[5] 张春昊,解滨,徐童童,张喜梅. 基于自然邻居搜索优化策略的密度峰值聚类算法[J]. 《山东大学学报(理学版)》, 2025, 60(1): 29-44.
[6] 吕安涛,高勇斌,韩汶,董莹,钟振方,孟庆春. 基于博弈论组合赋权-TOPSIS法的交通运输企业综合信用评价[J]. 《山东大学学报(理学版)》, 2024, 59(9): 88-97.
[7] 刘淼,彭家寅,汤建钢. 弱测量下噪声环境的多粒子短距离隐形传态[J]. 《山东大学学报(理学版)》, 2024, 59(8): 103-112.
[8] 刘梦迪,张贤勇,莫智文. 基于改进距离测度的概率犹豫模糊多属性群决策新方法[J]. 《山东大学学报(理学版)》, 2024, 59(3): 118-126.
[9] 刘欢,强会英,王洪申,白羽. 树图的2-距离和可区别染色[J]. 《山东大学学报(理学版)》, 2024, 59(2): 47-52, 58.
[10] 李侦瑷,韦慧,陈馨. 基于双目标的MNSGA-Ⅱ算法求解非线性方程组[J]. 《山东大学学报(理学版)》, 2024, 59(10): 22-29.
[11] 罗兴隆,贺兴时,周洁,杨新社. 基于非洲秃鹫优化算法改进的密度峰值聚类[J]. 《山东大学学报(理学版)》, 2024, 59(1): 46-55,71.
[12] 周宇,周礼刚,林志超,徐鑫. 概率q阶犹豫模糊TODIM方法及其应用[J]. 《山东大学学报(理学版)》, 2023, 58(6): 9-17.
[13] 刘胜强,马宁涓. 异质性传染病模型峰值和达峰时间研究[J]. 《山东大学学报(理学版)》, 2023, 58(10): 1-12.
[14] 韩露,郭鑫垚,魏巍,梁吉业. 基于约束分层加权的多度量学习算法[J]. 《山东大学学报(理学版)》, 2022, 57(4): 12-20.
[15] 吴一凡,王广富. 平面四角链距离谱半径的极图[J]. 《山东大学学报(理学版)》, 2022, 57(2): 84-91.
Viewed
Full text


Abstract

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