On the acyclic point-connectivity of the n-cube
The acyclic point-connectivity of a graph G, denoted α(G), is the minimum number of points whose removal from G results in an acyclic graph. In a 1975 paper, Harary stated erroneously that α(Qn)=2n−1−1 where Qn denotes the n-cube. We prove that for n>4, 7⋅2n−4≤α(Qn)≤2n−1−2n−y−2, where y=[log2(n−1...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
1982-01-01
|
| Series: | International Journal of Mathematics and Mathematical Sciences |
| Subjects: | |
| Online Access: | http://dx.doi.org/10.1155/S0161171282000684 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832556115364151296 |
|---|---|
| author | John Banks John Mitchem |
| author_facet | John Banks John Mitchem |
| author_sort | John Banks |
| collection | DOAJ |
| description | The acyclic point-connectivity of a graph G, denoted α(G), is the minimum number of points whose removal from G results in an acyclic graph. In a 1975 paper, Harary stated erroneously that α(Qn)=2n−1−1 where Qn denotes the n-cube. We prove that for n>4, 7⋅2n−4≤α(Qn)≤2n−1−2n−y−2, where y=[log2(n−1)]. We show that the upper bound is obtained for n≤8 and conjecture that it is obtained for all n. |
| format | Article |
| id | doaj-art-5e1262a051f44c3bb221b589d0b18607 |
| institution | Kabale University |
| issn | 0161-1712 1687-0425 |
| language | English |
| publishDate | 1982-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | International Journal of Mathematics and Mathematical Sciences |
| spelling | doaj-art-5e1262a051f44c3bb221b589d0b186072025-02-03T05:46:20ZengWileyInternational Journal of Mathematics and Mathematical Sciences0161-17121687-04251982-01-015473774410.1155/S0161171282000684On the acyclic point-connectivity of the n-cubeJohn Banks0John Mitchem1Department of Mathematics, University of California, Santa Cruz, Santa Cruz 95064, California, USADepartment of Mathematics and Computer Science, San Jose State University, San Jose 95192, California, USAThe acyclic point-connectivity of a graph G, denoted α(G), is the minimum number of points whose removal from G results in an acyclic graph. In a 1975 paper, Harary stated erroneously that α(Qn)=2n−1−1 where Qn denotes the n-cube. We prove that for n>4, 7⋅2n−4≤α(Qn)≤2n−1−2n−y−2, where y=[log2(n−1)]. We show that the upper bound is obtained for n≤8 and conjecture that it is obtained for all n.http://dx.doi.org/10.1155/S0161171282000684n-cubeanalytic point-connectivity. |
| spellingShingle | John Banks John Mitchem On the acyclic point-connectivity of the n-cube International Journal of Mathematics and Mathematical Sciences n-cube analytic point-connectivity. |
| title | On the acyclic point-connectivity of the n-cube |
| title_full | On the acyclic point-connectivity of the n-cube |
| title_fullStr | On the acyclic point-connectivity of the n-cube |
| title_full_unstemmed | On the acyclic point-connectivity of the n-cube |
| title_short | On the acyclic point-connectivity of the n-cube |
| title_sort | on the acyclic point connectivity of the n cube |
| topic | n-cube analytic point-connectivity. |
| url | http://dx.doi.org/10.1155/S0161171282000684 |
| work_keys_str_mv | AT johnbanks ontheacyclicpointconnectivityofthencube AT johnmitchem ontheacyclicpointconnectivityofthencube |