An independent set in a graph G is a set of pairwise nonadjacent vertices, and the maximum size, alpha(G), of an independent set in G is called the independence number.
Given a graph G and weight matrix A of G with entries from some field F, the maximum dimension of an A-isotropic subspace, known as the Witt index of A, is an upper bound on alpha(G). Since any weight matrix can be used, it is natural to seek the minimum upper bound on the independence number of G that can be achieved by a weight matrix. This
minimum, iota_F^*(G), is called the minimum Witt index of G over F, and the resulting bound, alpha(G)<= iota_F^*(G), is called
the isotropic bound.
When F is finite, the possible values of iota_F^*(G) are determined and the graphs that attain the isotropic bound are characterized. The characterization is given in terms of graph classes CC(n,t,c)
and CK(n,t,k) constructed from certain spanning subgraphs called C(n,t,c)-graphs and K(n,t,k)-graphs. Here t is the term rank
of the adjacency matrix of G.
When F=R, the isotropic bound is known as the Cvetkovi\'c bound. It is shown that it is sufficient to consider a finite number of
weight matrices A when determining iota_R^*(G) and that, in many cases, two weight values suffice. For example, if the vertex set of G can be covered by alpha(G) cliques, then G attains the Cvetkovi\'c bound with a weight matrix with two weight values.
Inequalities on alpha and iota_F^* resulting from graph operations such as sums, products, vertex deletion, and vertex identification are examined and, in some cases, conditions that imply equality are proved. The equalities imply that the problem of determining whether or not alpha(G)=iota_F^*(G) can be reduced to that of determining iota_F^*(H) for certain crucial graphs H found from G. / Thesis (Ph.D, Mathematics & Statistics) -- Queen's University, 2007-09-04 15:38:47.57
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:OKQ.1974/682 |
| Date | 17 September 2007 |
| Creators | Elzinga, Randall J. |
| Contributors | Queen's University (Kingston, Ont.). Theses (Queen's University (Kingston, Ont.)) |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English, English |
| Detected Language | English |
| Type | Thesis |
| Format | 521378 bytes, application/pdf |
| Rights | This publication is made available by the authority of the copyright owner solely for the purpose of private study and research and may not be copied or reproduced except as permitted by the copyright laws without written authority from the copyright owner. |
| Relation | Canadian theses |
Page generated in 0.0027 seconds