Name
Abstract | ||
|---|---|---|
A set S of vertices of a graph G is exponentially independent if, for every vertex u in S,Sigma(v is an element of\{u})(1/2)(dist(G, S)(u, v)-1) < 1,where dist((G, S))(u, v) is the distance between u and v in the graph G-(S\{u, v}). The exponential independence number alpha(e)(G) of G is the maximum order of an exponentially independent set in G. In the present paper we present several bounds on this parameter and highlight some of the many related open problems. In particular, we prove that subcubic graphs of order n have exponentially independent sets of order Omega(n/log(2)(n)), that the infinite cubic tree has no exponentially independent set of positive density, and that subcubic trees of order n have exponentially independent sets of order (n + 3)/4. (C) 2021 Elsevier B.V. All rights reserved. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1016/j.disc.2021.112439 | DISCRETE MATHEMATICS |
Keywords | DocType | Volume |
Exponential independence, Exponential domination | Journal | 344 |
Issue | ISSN | Citations |
8 | 0012-365X | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Stéphane Bessy | 1 | 117 | 19.68 |
| Johannes Pardey | 2 | 0 | 0.68 |
| Dieter Rautenbach | 3 | 946 | 138.87 |