CYCLE SPACES OF GRAPHS ON THE SPHERE AND THE PROJECTIVE PLANE

Abstract

Abstract:

Cycle base theory of a graph has been well studied in abstract mathematical
field such matroid theory as Whitney and Tutte did and found many applications in prat-
ical uses such as electric circuit theory and structure analysis, etc. In this paper graph
embedding theory is used to investigate cycle base structures of a 2-(edge)-connected graph
on the sphere and the projective plane and it is shown that short cycles do generate the
cycle spaces in the case of “small face-embeddings”. As applications the authors find the
exact formulae for the minimum lengthes of cycle bases of some types of graphs and present
several known results. Infinite examples shows that the conditions in their main results are
best possible and there are many 3-connected planar graphs whose minimum cycle bases
can not be determined by the planar formulae but may be located by re-embedding them
into the projective plane.

Key words: Cycle base;facial cycle;graph embedding

CLC Number:

05C10

LIN Han, LIU Pan-Pei, MA De-Ju, LEI Dun-Jie. CYCLE SPACES OF GRAPHS ON THE SPHERE AND THE PROJECTIVE PLANE[J].Acta mathematica scientia,Series B, 2005, 25(1): 41-49.

Trendmd

References

[1] Bondy J A, Murty U S R. Graph theory with applications. London: Macmillan, 1978

[2] Casell A C, et al. Cycle bases of minimum measure for the strural analysis of skeletal structures by the
flexibility method. Proc Roy Soc London Ser A, 1976, 35: 61-70

[3] Chua L O, Chen L. On optimally sparse cycle and coboundary basis for a linear graph. IEEE Trans Circuit
Theory, 1973, CT-20: 495-503

[4] Downs G D, et al. Review of ring perception algorithms for chemical graphs. J Chem Inf Comput Sci,
1989, 29: 172-187

[5] Freier S M, et al. Improved free-energy parameters for predictions of RNA duplex stability. Proc Natl
Acad Sci (USA), 1986, 83: 9373-9377

[6] Hartvigsen D, Zemel E. Is every cycle base fundamental? J of Graph Theory, 1989, 13: 117-137

[7] Hartvigsen D, Mardon R. When do short cycles generate the cycle space? J Combin Theory, 1993, 57B:
88-99

[8] Phillip Hall. On representatives of subsets. London Math Soc, 1935, 10: 26-30

[9] Horton J D. A polynomial-time algorithm to find the shortest cycle base of a graph. SIAM J Comput,
1987, 16: 359-366

[10] Kaveh A. Structural Mechanics: Graph and Matrix Mathods. Exeter, UK: Research studies Press, 1992

[11] Leydold J, et al. Minimal cycle bases of outerplanar graphs. Electronic J Combin, 1998, 5#16: 14

[12] Liu G. On connectivities of tree graphs. J of Graph Theory, 1988, 12: 453-459

[13] Liu Y P. Embeddibility in graphs. Boston: Kluwer Acad Publishers, 1995

[14] Tutte W. A homotopy theorem for matroids I, II. Trans AMS, 1958, 88: 144-160; 161-174

[15] Vismara P. Union of all the minimum cycle bases of a graph. Electronic J Combin, 1997, 4 #9: 15

[16] Voss V -J. Cycles and bridges in graphs. Dordrecht: Kluwer, 1990

[17] Welsh C J A. Matroid theory. Acad Press, 1976

[18] White A L. Theory of matroids. Cambridge Univ Press, 1986

[19] White A L. Combinatorial geometries. Cambridge Univ Press, 1987

[20] White A L. Matroids application. Cambridge Univ Press, 1992

[21] Whitney H. On abstract properties of linear dependence. Amer J Math, 1935, 57: 509-533