Download PDF - Some additions to the theory of star partitions of graphsAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

Some additions to the theory of star partitions of graphs

Authors 1, 2, 1, 2

Affiliations

  1. Mathematics and Statistics Group, Department of Computing Science and Mathematics, University of Stirling, Scotland FK9 4LA, United Kingdom
  2. 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

ENG
graph, eigenvalues, eigenspaces, star partitions

Bibliography

  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.
Discussiones Mathematicae Graph Theory
1999/19/2
Export to PBN, Opens in new tab
Pages:
119-134
Main language of publication
English
Received
1999-01-04
Accepted
1999-08-06
Published
1999

DOI: 10.7151/dmgt.1089

Exact and natural sciences