Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 1190.05084
Sciriha, Irene
Maximal core size in singular graphs. (English)
[J] Ars Math. Contemp. 2, No. 2, 217-229 (2009). ISSN 1855-3966; ISSN 1855-3974/e

Summary: A graph $G$ is singular of nullity $\eta $ if the nullspace of its adjacency matrix $G$ has dimension $\eta $. Such a graph contains $\eta $ cores determined by a basis for the nullspace of $G$. These are induced subgraphs of singular configurations, the latter occurring as induced subgraphs of $G$. We show that there exists a set of $\eta $ distinct vertices representing the singular configurations. We also explore how the nullity controls the size of the singular substructures and characterize those graphs of maximal nullity containing a substructure reaching maximal size.

MSC 2000:: *05C50 Graphs and matrices
05C60 Isomorphism problems (graph theory)
05B20 (0,1)-matrices (combinatorics)

Keywords: adjacency matrix; nullity; extremal singular graphs; singular configurations; core width

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]