Loading...
Please wait, while we are loading the content...
Similar Documents
Contractible and non-contractible non-edges in 2-connected graphs Tsz Lung
| Content Provider | Semantic Scholar |
|---|---|
| Author | Chan |
| Copyright Year | 2019 |
| Abstract | In this paper, we prove that for any 2-connected finite graph of order n (n ≥ 6), the number of contractible non-edges is at most n(n−4) 2 . All the extremal graphs with at least eight vertices are characterized. We also prove that for any 2-connected finite graph of order n that is not a cycle, the number of non-contractible non-edges is at most (n−1)(n−4) 2 . This bound is attained precisely by a cycle with exactly one chord between two vertices at distance two apart. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://ajc.maths.uq.edu.au/pdf/73/ajc_v73_p346.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
