JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2015, Vol. 50 ›› Issue (02): 38-42.doi: 10.6040/j.issn.1671-9352.0.2014.324

Previous Articles     Next Articles

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)

526

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

CLC Number: 

  • 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] XU Wei-cheng, LI Xin-peng. Generalized Cav(u)theorem for repeated games with incomplete information on one side [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(4): 42-45.
[2] HUANG Dong, XU Bo, XU Kan, LIN Hong-fei, YANG Zhi-hao. Short text clustering based on word embeddings and EMD [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(7): 66-72.
[3] ZHU Xiao-ying, PANG Shi-you. On the maximal eccentric distance sum of tree with given domination number [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(2): 30-36.
[4] . An approach of detecting LDoS attacks based on the euclidean distance of available bandwidth in cloud computing [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(9): 92-100.
[5] ZHAI Peng, LI Deng-dao. The fuzzy clustering algorithm based on inclusion index of Gausian membership function [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(5): 102-105.
[6] LIU Ying-ying, LIU Pei-yu, WANG Zhi-hao, LI Qing-qing, ZHU Zhen-fang. A text clustering algorithm based on find of density peaks [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(1): 65-70.
[7] SANG Le-yuan, XU Xin-feng, ZHANG Jing, HUANG De-gen. New microblog sentiment lexicon judgment based on generalized Jaccard coefficient [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2015, 50(07): 71-75.
[8] LIN Hong-kang1,2, LI Yu-ying1,2, XIONG Guo-min3. Dynamic data distance and geometric identification-recovery [J]. J4, 2012, 47(8): 92-97.
[9] HUANG Lin-sheng1, DENG Zhi-hong1,2, TANG Shi-wei1,2, WANG Wen-qing3, CHEN Ling3. A Chinese organization′s full name and matching abbreviation  algorithm based on edit-distance [J]. J4, 2012, 47(5): 43-48.
[10] GAO Jian, CAO Yong-lin. Constructing 2-generator quasi-twisted codes over finite fields [J]. J4, 2012, 47(10): 31-33.
[11] ZHAO Wei-hua1, FENG Yu2, LI Ze-an3. Influence diagnostics for generalized binomial regression models [J]. J4, 2011, 46(1): 97-103.
[12] ZHANG Xue-feng1, LIU Peng1,2. An improved K-means algorithm by weighted distance based on maximum between-cluster variation [J]. J4, 2010, 45(7): 28-33.
[13] MA Bao-lin1,2， CHEN Xiang-en1*， LIU Juan2. 2-distance coloring of strong product of graphs [J]. J4, 2010, 45(3): 66-70.
[14] CUI Mei-hua. The D-conditional truth degree of formulas and approximate reasoning in the  G3 propositional logic system [J]. J4, 2010, 45(11): 52-58.
[15] YUAN Pan-Chi, Zhang-Xin-Fang. Study of the conditional probability truth degree of formulas in the Gödel logic system [J]. J4, 2009, 44(9): 70-74.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd