Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
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
Search
Partner of
