外平面图的平方图的点荫度

外平面图的平方图的点荫度

马刚¹,吴建良¹,方峻峰¹,

1. 山东大学数学与系统科学学院, 山东济南250100; 2. 山东省烟草公司信息中心，山东济南250100

收稿日期:2005-12-21 修回日期:1900-01-01 出版日期:2006-10-24 发布日期:2006-10-24
通讯作者: 马刚

The vertex arboricity of the square of an outerplanar graph

MA Gangsup>1,WU Jian-liang¹,FANG Jun-feng¹,

1. School of Math., and System Sci., Shandong Univ., Jinan 250100, Shandong, China;

Received:2005-12-21 Revised:1900-01-01 Online:2006-10-24 Published:2006-10-24
Contact: MA Gang

摘要/Abstract

摘要： 图G的平方图G2是以V(G)作为它的点集，两个点在G2中相邻当且仅当它们在G中的距离至多为2.证明了：若G是一个最大度Δ6的外平面图,则G2的点荫度va(G2)=「Δ+12?;特别地，一棵树T的平方图T2的点荫度va(T2)=「Δ+12?.

关键词: 树, 外平面图, 点荫度 , 平方图

Abstract: The square graph G2 of agraph G is the graph defined on the vertex set V(G) such that two vertices are adjacent in G2 if and only if the distance between them is at most 2. It is proved that if G is an outerplanar graph with maximum degree Δ6, then the vertexarboricity va(G2) of G2 is 「Δ+12?; In particular, if T is a tree, the vertex arboricity va(T2)=「Δ+12?.

Key words: vertex arboricity , square graph, outerplanar graph, tree

马刚,吴建良,方峻峰, . 外平面图的平方图的点荫度[J]. J4, 2006, 41(4): 65-67 .

MA Gangsup>,WU Jian-liang,FANG Jun-feng, . The vertex arboricity of the square of an outerplanar graph[J]. J4, 2006, 41(4): 65-67 .

参考文献

相关文章 15

[1]	王倩. k-连通图中生成树和完美匹配上的可收缩边[J]. 山东大学学报（理学版）, 2016, 51(8): 29-34.
[2]	朱海洋,顾毓,吕新忠. 平面图的平方染色数的一个新上界[J]. 山东大学学报（理学版）, 2016, 51(2): 94-101.
[3]	伊文慧,王延平,王华田,马雪松,王文波. 酚酸类化感物质对杨树人工林土壤硝化作用的影响[J]. 山东大学学报（理学版）, 2016, 51(1): 27-35.
[4]	马丽菲,莫倩,杜辉. 面向中文短影评的分类技术研究[J]. 山东大学学报（理学版）, 2016, 51(1): 52-57.
[5]	孙林, 蔡华. 嵌入曲面的图的点荫度[J]. 山东大学学报（理学版）, 2015, 50(02): 38-42.
[6]	谭红叶, 赵健, 陈千. 基于不一致的汉语句法树库潜在错误查找[J]. 山东大学学报（理学版）, 2015, 50(01): 26-30.
[7]	唐波, 陈光, 王星雅, 王非, 陈小慧. 微博新词发现及情感倾向判断分析[J]. 山东大学学报（理学版）, 2015, 50(01): 20-25.
[8]	卢琦蓓1,2,郭飞鹏3. 基于改进型FP-Tree的分布式关联分类算法[J]. 山东大学学报（理学版）, 2014, 49(1): 71-75.
[9]	刘文卓, 曹天杰, 黄石. 一种高效的多副本数据持有性证明方案[J]. 山东大学学报（理学版）, 2014, 49(09): 160-165.
[10]	张聪, 于洪. 一种三支决策软增量聚类算法[J]. 山东大学学报（理学版）, 2014, 49(08): 40-47.
[11]	秦柱南, 孙超, 韩义, 曹帮华, 马永升, 贾波. 株行距配置对杨树生长及光合特性的影响[J]. 山东大学学报（理学版）, 2014, 49(07): 1-6.
[12]	王宏宇,姚兵*,杨超. 可拆分树的边魔幻全标号性[J]. 山东大学学报（理学版）, 2014, 49(04): 29-37.
[13]	孙德荣,徐兰. 恰有三个主特征值的树[J]. J4, 2013, 48(6): 23-28.
[14]	赵建诚1,曹帮华1*,吴丽云2,赵珮1,侯蕊1,牛庆霖1. 杨树无性系根系特征及地上与地下部分相关性研究[J]. J4, 2013, 48(11): 7-13.
[15]	蔡裕华,魏凤英*. 度量空间的概率近似算法[J]. J4, 2013, 48(09): 51-55.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed