DC Field | Value | Language |
---|---|---|
dc.contributor.author | Cioaba, SM | - |
dc.contributor.author | Kim, K | - |
dc.contributor.author | Koolen, JH | - |
dc.date.accessioned | 2016-03-31T08:38:06Z | - |
dc.date.available | 2016-03-31T08:38:06Z | - |
dc.date.created | 2013-03-27 | - |
dc.date.issued | 2012-05 | - |
dc.identifier.issn | 0097-3165 | - |
dc.identifier.other | 2012-OAK-0000027220 | - |
dc.identifier.uri | https://oasis.postech.ac.kr/handle/2014.oak/15706 | - |
dc.description.abstract | In this paper, we study a conjecture of Andries E. Brouwer from 1996 regarding the minimum number of vertices of a strongly regular graph whose removal disconnects the graph into non-singleton components. We show that strongly regular graphs constructed from copolar spaces and from the more general spaces called Delta-spaces are counter-examples to Brouwer's Conjecture. Using J.I. Hall's characterization of finite reduced copolar spaces, we find that the triangular graphs T (m), the symplectic graphs Sp(2r,q) over the field F-q (for any q prime power), and the strongly regular graphs constructed from the hyperbolic quadrics O+(2r, 2) and from the elliptic quadrics O-(2r, 2) over the field F-2, respectively, are counter-examples to Brouwer's Conjecture. For each of these graphs, we determine precisely the minimum number of vertices whose removal disconnects the graph into non-singleton components. While we are not aware of an analogue of Hall's characterization theorem for Delta-spaces, we show that complements of the point graphs of certain finite generalized quadrangles are point graphs of Delta-spaces and thus, yield other counterexamples to Brouwer's Conjecture. We prove that Brouwer's Conjecture is true for many families of strongly regular graphs including the conference graphs, the generalized quadrangles GQ(q, q) graphs, the lattice graphs, the Latin square graphs, the strongly regular graphs with smallest eigen-value -2 (except the triangular graphs) and the primitive strongly regular graphs with at most 30 vertices except for few cases. We leave as an open problem determining the best general lower bound for the minimum size of a disconnecting set of vertices of a strongly regular graph, whose removal disconnects the graph into non-singleton components. (C) 2012 Elsevier Inc. All rights reserved. | - |
dc.description.statementofresponsibility | X | - |
dc.language | English | - |
dc.publisher | ACADEMIC PRESS INC ELSEVIER SCIENCE | - |
dc.relation.isPartOf | JOURNAL OF COMBINATORIAL THEORY SERIES A | - |
dc.subject | Strongly regular graphs | - |
dc.subject | Connectivity | - |
dc.subject | Eigenvalues | - |
dc.subject | Distance regular graphs | - |
dc.subject | Copolar spaces | - |
dc.subject | Delta spaces | - |
dc.subject | EIGENVALUES | - |
dc.title | On a conjecture of Brouwer involving the connectivity of strongly regular graphs | - |
dc.type | Article | - |
dc.contributor.college | 수학과 | - |
dc.identifier.doi | 10.1016/J.JCTA.2012.01.001 | - |
dc.author.google | Cioaba, SM | - |
dc.author.google | Kim, K | - |
dc.author.google | Koolen, JH | - |
dc.relation.volume | 119 | - |
dc.relation.issue | 4 | - |
dc.relation.startpage | 904 | - |
dc.relation.lastpage | 922 | - |
dc.contributor.id | 10200295 | - |
dc.relation.journal | JOURNAL OF COMBINATORIAL THEORY SERIES A | - |
dc.relation.index | SCI급, SCOPUS 등재논문 | - |
dc.relation.sci | SCI | - |
dc.collections.name | Journal Papers | - |
dc.type.rims | ART | - |
dc.identifier.bibliographicCitation | JOURNAL OF COMBINATORIAL THEORY SERIES A, v.119, no.4, pp.904 - 922 | - |
dc.identifier.wosid | 000301027300005 | - |
dc.date.tcdate | 2019-01-01 | - |
dc.citation.endPage | 922 | - |
dc.citation.number | 4 | - |
dc.citation.startPage | 904 | - |
dc.citation.title | JOURNAL OF COMBINATORIAL THEORY SERIES A | - |
dc.citation.volume | 119 | - |
dc.contributor.affiliatedAuthor | Koolen, JH | - |
dc.identifier.scopusid | 2-s2.0-84862793578 | - |
dc.description.journalClass | 1 | - |
dc.description.journalClass | 1 | - |
dc.description.wostc | 6 | - |
dc.description.scptc | 4 | * |
dc.date.scptcdate | 2018-05-121 | * |
dc.type.docType | Article | - |
dc.subject.keywordAuthor | Strongly regular graphs | - |
dc.subject.keywordAuthor | Connectivity | - |
dc.subject.keywordAuthor | Eigenvalues | - |
dc.subject.keywordAuthor | Distance regular graphs | - |
dc.subject.keywordAuthor | Copolar spaces | - |
dc.subject.keywordAuthor | Delta spaces | - |
dc.relation.journalWebOfScienceCategory | Mathematics | - |
dc.description.journalRegisteredClass | scie | - |
dc.description.journalRegisteredClass | scopus | - |
dc.relation.journalResearchArea | Mathematics | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
library@postech.ac.kr Tel: 054-279-2548
Copyrights © by 2017 Pohang University of Science ad Technology All right reserved.