Geodesic
An upper bound on the basis number of the powers of the complete graphs
Czechoslovak Mathematical Journal, Tome 51 (2001) no. 2, pp. 231-238

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

MR   Zbl

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$.
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$.
Classification : 05C10, 05C35, 05C38, 05C99 
Alsardary, Salar Y. An upper bound on the basis number of the powers of the complete graphs. Czechoslovak Mathematical Journal, Tome 51 (2001) no. 2, pp. 231-238. http://geodesic.mathdoc.fr/item/CMJ_2001_51_2_a1/
@article{CMJ_2001_51_2_a1,
     author = {Alsardary, Salar Y.},
     title = {An upper bound on the basis number of the powers of the complete graphs},
     journal = {Czechoslovak Mathematical Journal},
     pages = {231--238},
     year = {2001},
     volume = {51},
     number = {2},
     mrnumber = {1844307},
     zbl = {0977.05134},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMJ_2001_51_2_a1/}
}
TY  - JOUR
AU  - Alsardary, Salar Y.
TI  - An upper bound on the basis number of the powers of the complete graphs
JO  - Czechoslovak Mathematical Journal
PY  - 2001
SP  - 231
EP  - 238
VL  - 51
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/CMJ_2001_51_2_a1/
LA  - en
ID  - CMJ_2001_51_2_a1
ER  - 
%0 Journal Article
%A Alsardary, Salar Y.
%T An upper bound on the basis number of the powers of the complete graphs
%J Czechoslovak Mathematical Journal
%D 2001
%P 231-238
%V 51
%N 2
%U http://geodesic.mathdoc.fr/item/CMJ_2001_51_2_a1/
%G en
%F CMJ_2001_51_2_a1

[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

[3] A. A. Ali: The basis number of complete multipartite graphs. Ars Combin. 28 (1989), 41–49. | MR | Zbl

[4] A. A. Ali: The basis number of the direct products of paths and cycles. Ars Combin. 27 (1989), 155–164. | MR

[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

[6] Salar Y. Alsardary and A. A. Ali: The basis number of some special non-planar graphs. Czechoslovak Math. J (to appear). | MR

[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 | MR

[8] J. A. Bondy and S. R. Murty: Graph Theory with Applications. Amer. Elsevier, New York, 1976. | MR

[9] S. MacLane: A combinatorial condition for planar graphs. Fund. Math. 28 (1937), 22–32. | Zbl

[10] E. F. Schmeichel: The basis number of a graph. J. Combin. Theory, Ser. B. 30 (1981), 123–129. | DOI | MR | Zbl

[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 | MR | Zbl