An upper bound on the basis number of the powers of the complete graphs

Salar Y. Alsardary

Czechoslovak Mathematical Journal (2001)

  • Volume: 51, Issue: 2, page 231-238
  • ISSN: 0011-4642

Abstract

top
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 ≤ 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 2 d + 1 .

How to cite

top

Alsardary, Salar Y.. "An upper bound on the basis number of the powers of the complete graphs." Czechoslovak Mathematical Journal 51.2 (2001): 231-238. <http://eudml.org/doc/30631>.

@article{Alsardary2001,
abstract = {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$.},
author = {Alsardary, Salar Y.},
journal = {Czechoslovak Mathematical Journal},
keywords = {planar graph; complete graph; power of a graph; basis number of a graph},
language = {eng},
number = {2},
pages = {231-238},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {An upper bound on the basis number of the powers of the complete graphs},
url = {http://eudml.org/doc/30631},
volume = {51},
year = {2001},
}

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
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 51
IS - 2
SP - 231
EP - 238
AB - 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$.
LA - eng
KW - planar graph; complete graph; power of a graph; basis number of a graph
UR - http://eudml.org/doc/30631
ER -

References

top
  1. On the basis number of a graph, Dirasat 14 (1987), 43–51. (1987) 
  2. The basis number of the join of graphs, Arab J. Math. 10 (1989), 21–33. (1989) Zbl0806.05043
  3. The basis number of complete multipartite graphs, Ars Combin. 28 (1989), 41–49. (1989) Zbl0728.05058MR1039129
  4. The basis number of the direct products of paths and cycles, Ars Combin. 27 (1989), 155–164. (1989) MR0989461
  5. The basis number of the cartesian product of some graphs, J. Indian Math. Soc. (N.S.) 58 (1992), 123–134. (1992) MR1207033
  6. The basis number of some special non-planar graphs, Czechoslovak Math. J (to appear). (to appear) MR1983447
  7. 10.1016/0095-8956(82)90061-2, J. Combin. Theory, Ser. B 33 (1982), 95–100. (1982) MR0685059DOI10.1016/0095-8956(82)90061-2
  8. Graph Theory with Applications, Amer. Elsevier, New York, 1976. (1976) MR0411988
  9. A combinatorial condition for planar graphs, Fund. Math. 28 (1937), 22–32. (1937) Zbl0015.37501
  10. 10.1016/0095-8956(81)90057-5, J. Combin. Theory, Ser. B. 30 (1981), 123–129. (1981) Zbl0385.05031MR0615307DOI10.1016/0095-8956(81)90057-5
  11. 10.1112/jlms/50.3.465, J. London Math. Soc. II, Ser. 50 (1994), 465–476. (1994) Zbl0814.05043MR1299451DOI10.1112/jlms/50.3.465

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.