# Article

Full entry | PDF   (0.2 MB)
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\$.
References:
[1] A. A. Ali and Salar Y. Alsardary: On the basis number of a graph. Dirasat 14 (1987), 43–51.
[2] A. A. Ali: The basis number of the join of graphs. Arab J. Math. 10 (1989), 21–33. Zbl 0806.05043
[3] A. A. Ali: The basis number of complete multipartite graphs. Ars Combin. 28 (1989), 41–49. MR 1039129 | Zbl 0728.05058
[4] A. A. Ali: The basis number of the direct products of paths and cycles. Ars Combin. 27 (1989), 155–164. MR 0989461
[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
[6] Salar Y. Alsardary and A. A. Ali: The basis number of some special non-planar graphs. Czechoslovak Math. J (to appear). MR 1983447
[7] J. A. Banks and E. F. Schmeichel: The basis number of the \$n\$-cube. J. Combin. Theory, Ser. B 33 (1982), 95–100. DOI 10.1016/0095-8956(82)90061-2 | MR 0685059
[8] J. A. Bondy and S. R. Murty: Graph Theory with Applications. Amer. Elsevier, New York, 1976. MR 0411988
[9] S. MacLane: A combinatorial condition for planar graphs. Fund. Math. 28 (1937), 22–32. Zbl 0015.37501
[10] E. F. Schmeichel: The basis number of a graph. J. Combin. Theory, Ser. B. 30 (1981), 123–129. DOI 10.1016/0095-8956(81)90057-5 | MR 0615307 | Zbl 0385.05031
[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. DOI 10.1112/jlms/50.3.465 | MR 1299451 | Zbl 0814.05043

Partner of