Previous |  Up |  Next

Article

Title: An upper bound on the basis number of the powers of the complete graphs (English)
Author: Alsardary, Salar Y.
Language: English
Journal: Czechoslovak Mathematical Journal
ISSN: 0011-4642 (print)
ISSN: 1572-9141 (online)
Volume: 51
Issue: 2
Year: 2001
Pages: 231-238
Summary lang: English
.
Category: math
.
Summary: The basis number of a graph $G$ is defined by Schmeichel to be the least integer $h$ such that $G$ has an $h$-fold basis for its cycle space. MacLane showed that a graph is planar if and only if its basis number is $\le 2$. Schmeichel proved that the basis number of the complete graph $K_n$ is at most $3$. We generalize the result of Schmeichel by showing that the basis number of the $d$-th power of $K_n$ is at most $2d+1$. (English)
MSC: 05C10
MSC: 05C35
MSC: 05C38
MSC: 05C99
idZBL: Zbl 0977.05134
idMR: MR1844307
.
Date available: 2009-09-24T10:41:57Z
Last updated: 2020-07-03
Stable URL: http://hdl.handle.net/10338.dmlcz/127644
.
Reference: [1] A. A. Ali and Salar Y. Alsardary: On the basis number of a graph.Dirasat 14 (1987), 43–51.
Reference: [2] A. A. Ali: The basis number of the join of graphs.Arab J. Math. 10 (1989), 21–33. Zbl 0806.05043
Reference: [3] A. A. Ali: The basis number of complete multipartite graphs.Ars Combin. 28 (1989), 41–49. Zbl 0728.05058, MR 1039129
Reference: [4] A. A. Ali: The basis number of the direct products of paths and cycles.Ars Combin. 27 (1989), 155–164. MR 0989461
Reference: [5] A. A. Ali and G. T. Marougi: The basis number of the cartesian product of some graphs.J. Indian Math. Soc. (N.S.) 58 (1992), 123–134. MR 1207033
Reference: [6] Salar Y. Alsardary and A. A. Ali: The basis number of some special non-planar graphs.Czechoslovak Math. J (to appear). MR 1983447
Reference: [7] J. A. Banks and E. F. Schmeichel: The basis number of the $n$-cube.J. Combin. Theory, Ser. B 33 (1982), 95–100. MR 0685059, 10.1016/0095-8956(82)90061-2
Reference: [8] J. A. Bondy and S. R. Murty: Graph Theory with Applications.Amer. Elsevier, New York, 1976. MR 0411988
Reference: [9] S. MacLane: A combinatorial condition for planar graphs.Fund. Math. 28 (1937), 22–32. Zbl 0015.37501
Reference: [10] E. F. Schmeichel: The basis number of a graph.J. Combin. Theory, Ser. B. 30 (1981), 123–129. Zbl 0385.05031, MR 0615307, 10.1016/0095-8956(81)90057-5
Reference: [11] J. Wojciechowski: Long snakes in powers of the complete graph with an odd number of vertices.J. London Math. Soc. II, Ser. 50 (1994), 465–476. Zbl 0814.05043, MR 1299451, 10.1112/jlms/50.3.465
.

Files

Files Size Format View
CzechMathJ_51-2001-2_2.pdf 311.5Kb application/pdf View/Open
Back to standard record
Partner of
EuDML logo