# Some additions to the theory of star partitions of graphs

Francis K. Bell; Dragos Cvetković; Peter Rowlinson; Slobodan K. Simić

Discussiones Mathematicae Graph Theory (1999)

- Volume: 19, Issue: 2, page 119-134
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topFrancis K. Bell, et al. "Some additions to the theory of star partitions of graphs." Discussiones Mathematicae Graph Theory 19.2 (1999): 119-134. <http://eudml.org/doc/270753>.

@article{FrancisK1999,

abstract = {This paper contains a number of results in the theory of star partitions of graphs. We illustrate a variety of situations which can arise when the Reconstruction Theorem for graphs is used, considering in particular galaxy graphs - these are graphs in which every star set is independent. We discuss a recursive ordering of graphs based on the Reconstruction Theorem, and point out the significance of galaxy graphs in this connection.},

author = {Francis K. Bell, Dragos Cvetković, Peter Rowlinson, Slobodan K. Simić},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {graph; eigenvalues; eigenspaces; star partitions; galaxy graphs; star set},

language = {eng},

number = {2},

pages = {119-134},

title = {Some additions to the theory of star partitions of graphs},

url = {http://eudml.org/doc/270753},

volume = {19},

year = {1999},

}

TY - JOUR

AU - Francis K. Bell

AU - Dragos Cvetković

AU - Peter Rowlinson

AU - Slobodan K. Simić

TI - Some additions to the theory of star partitions of graphs

JO - Discussiones Mathematicae Graph Theory

PY - 1999

VL - 19

IS - 2

SP - 119

EP - 134

AB - This paper contains a number of results in the theory of star partitions of graphs. We illustrate a variety of situations which can arise when the Reconstruction Theorem for graphs is used, considering in particular galaxy graphs - these are graphs in which every star set is independent. We discuss a recursive ordering of graphs based on the Reconstruction Theorem, and point out the significance of galaxy graphs in this connection.

LA - eng

KW - graph; eigenvalues; eigenspaces; star partitions; galaxy graphs; star set

UR - http://eudml.org/doc/270753

ER -

## References

top- [1] G. Caporossi, D. Cvetković, P. Hansen, S. Simić, Variable neighborhood search for extremal graphs, 3: on the largest eigenvalue of color-constrained trees, to appear. Zbl1003.05058
- [2] D. Cvetković, Star partitions and the graph isomorphism problem, Linear and Multilinear Algebra 39 (1995) No. 1-2 109-132. Zbl0831.05043
- [3] D. Cvetković, M. Doob, H. Sachs, Spectra of Graphs (3rd edition, Johann Ambrosius Barth Verlag, Heidelberg, 1995). Zbl0824.05046
- [4] D. Cvetković, M. Petrić, A table of connected graphs on six vertices, Discrete Math. 50 (1984) 37-49, doi: 10.1016/0012-365X(84)90033-5. Zbl0533.05052
- [5] D. Cvetković, P. Rowlinson, S. Simić, Eigenspaces of Graphs (Cambridge University Press, Cambridge, 1997). Zbl0878.05057
- [6] D. Cvetković, P. Rowlinson, S.K. Simić, Graphs with least eigenvalue -2: the star complement technique, to appear. Zbl0982.05065
- [7] M. Doob, An inter-relation between line graphs, eigenvalues and matroids, J. Combin. Theory (B) 15 (1973) 40-50, doi: 10.1016/0095-8956(73)90030-0. Zbl0245.05125
- [8] M.N. Ellingham, Basic subgraphs and graph spectra, Australasian J. Combin. 8 (1993) 247-265. Zbl0790.05057
- [9] C.D. Godsil, Matching and walks in graphs, J. Graph Theory 5 (1981) 285-297, doi: 10.1002/jgt.3190050310.
- [10] E.L. Lawler, J.K. Lenstra, A.H.G. Rinnoy Kan, D.B. Schmoys, eds., The traveling salesman problem (John Wiley and Sons, Chichester - New York - Brisbane - Toronto - Singapore, 1985). Zbl0563.90075
- [11] P. Rowlinson, Dominating sets and eigenvalues of graphs, Bull. London Math. Soc. 26 (1994) 248-254, doi: 10.1112/blms/26.3.248. Zbl0806.05040
- [12] P. Rowlinson, Star sets and star complements in finite graphs: a spectral construction technique, in: Proc. DIMACS Workshop on Discrete Mathematical Chemistry (March 1998), to appear. Zbl0964.05041
- [13] P. Rowlinson, On graphs with multiple eigenvalues, Linear Algebra and Appl. 283 (1998) 75-85, doi: 10.1016/S0024-3795(98)10082-4. Zbl0931.05055
- [14] P. Rowlinson, Linear Algebra, in: eds. L.W. Beineke and R.J. Wilson, Graph Connections (Oxford Lecture Series in Mathematics and its Applications 5, Oxford University Press, Oxford, 1997) 86-99.
- [15] J.J. Seidel, Eutactic stars, in: eds. A. Hajnal and V.T. Sós, Combinatorics (North-Holland, Amsterdam, 1978) 983-999. Zbl0391.05050

## NotesEmbed ?

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