PDF

Discussiones Mathematicae Graph Theory 19(2) (1999) 119-134
DOI: https://doi.org/10.7151/dmgt.1089

SOME ADDITIONS TO THE THEORY OF STAR PARTITIONS OF GRAPHS

Francis K. Bell Mathematics and Statistics Group Department of Computing Science and Mathematics University of Stirling, Scotland FK9 4LA United Kingdom

Dragos Cvetković Department of Mathematics Faculty of Electrical Engineering University of Belgrade P.O. Box 35-54, 11120 Belgrade Yugoslavia

Peter Rowlinson Mathematics and Statistics Group Department of Computing Science and Mathematics University of Stirling, Scotland FK9 4LA United Kingdom

Slobodan K. Simić Department of Mathematics Faculty of Electrical Engineering University of Belgrade P.O. Box 35-54, 11120 Belgrade Yugoslavia

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.

Keywords: graph, eigenvalues, eigenspaces, star partitions.

1991 Mathematics Subject Classification: 05C50.

References

[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.
[2]	D. Cvetković, Star partitions and the graph isomorphism problem, Linear and Multilinear Algebra 39 (1995) No. 1-2 109-132.
[3]	D. Cvetković, M. Doob, H. Sachs, Spectra of Graphs (3rd edition, Johann Ambrosius Barth Verlag, Heidelberg, 1995).
[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.
[5]	D. Cvetković, P. Rowlinson, S. Simić, Eigenspaces of Graphs (Cambridge University Press, Cambridge, 1997).
[6]	D. Cvetković, P. Rowlinson, S.K. Simić, Graphs with least eigenvalue −2: the star complement technique, to appear.
[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.
[8]	M.N. Ellingham, Basic subgraphs and graph spectra, Australasian J. Combin. 8 (1993) 247-265.
[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).
[11]	P. Rowlinson, Dominating sets and eigenvalues of graphs, Bull. London Math. Soc. 26 (1994) 248-254, doi: 10.1112/blms/26.3.248.
[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.
[13]	P. Rowlinson, On graphs with multiple eigenvalues, Linear Algebra and Appl. 283 (1998) 75-85, doi: 10.1016/S0024-3795(98)10082-4.
[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.

Received 4 January 1999
Revised 6 August 1999