| 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 |
| . |
