|Table of Contents|

Upper Embeddability of 3-Edge-Connected Simple Graphs with Independence-Number≤5(PDF)

《南京师大学报（自然科学版）》[ISSN:1001-4616/CN:32-1239/N]

Issue:
2006年01期
Page:
17-20
Research Field:
数学
Publishing date:

Info

Title:
Upper Embeddability of 3-Edge-Connected Simple Graphs with Independence-Number≤5
Author(s):
Gao Yanbo~1; Ren Han~2
( 1. School of Science, N antong U nivers ity, N antong 226007, Ch ina)
( 2. Departm en t ofMathem atics, East Ch ina Norm alUn ivers ity, Shangh ai200062, Ch ina)
Keywords:
graph;  m axim um genus;  b ett i deficien cy;  upper em beddab le;  independen ce-number
PACS:
O157.5
DOI:
-
Abstract:
Com b ined w ith th e edge-connect ivity, th is paper investigates the relationsh ip b etw een the independence- numb er and the upper-emb eddab ility of a 3-edge-conn ected sim p le graph and obtain s the follow ing resu lt: LetG be a 3- edge-connected sim p le graph w ith α(G )≤ 5 (w here α(G ) is the indep endence-numb er ofG ) , th enG is upper embed- dab le, and two m in im al examp les are given in th e sen se that th ere are 3-edge-connected graphsw h ich are n ot upper em- beddab le.

References:

[ 1] Bondy J A, Murty U S R. G raph Theory w ith Applications[M ]. N ew York: E lsev ier Science, 1976.
[ 2] Stahl S. The embedd ing s of a graph a survey[ J]. J Graph Theory, 1978, 2: 275-298.
[ 3] No rdhaus E, S tew art B, W hite A T. On the max im um g enus of a g raph[ J]. Journal Comb inator ia l Theory Ser ies B, 1971, 11: 258-267.
[ 4] Xuong N H. H ow to dete rm ine the m ax im um g enus o f agraph[ J]. Journa l o f Comb inator ial Theory Series B, 1979, 26:217-225.
[ 5] Kundu S. Bounds on number of d isjo int spanning trees[ J]. Journa l Com binato rial Theory Se ries B, 1974, 17: 199-203.
[ 6] Junge rman M. A character ization of upper-embeddab le g raphs[ J] . Transactions o f the Am er ican M athema tica l Society,1978, 241: 401-406.
[ 7] Xuong N H. U pper-embeddab le g raphs and re lated top ics[ J]. Jou rnal o f Comb inator ia l Theory Se ries B, 1979, 26: 226-232.
[ 8] Nebesky L. A new character izations o f the m ax imum genus of graphs[ J]. Czechoslovak M ath J, 1981, 31( 106 ): 604-613.
[ 9] H uang Y Q, L iu Y P. An improvem ent of a theorem on the m ax im um genus for g raphs[ J]. M athem aticaApplicate, 1998, 11( 2): 109-112.
[ 10] H uang Y P, Liu Y P. The m ax imum genus of graphs with diam e ter three[ J]. Discrete Mathematics, 1999, 194( 1 /3):139-149.

Memo

Memo:
-
Last Update: 2013-05-05