Exponential independence in subcubic graphs
| Autor: | Johannes Pardey, Dieter Rautenbach, Stéphane Bessy |
|---|---|
| Přispěvatelé: | Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), Universität Ulm - Ulm University [Ulm, Allemagne] |
| Rok vydání: | 2021 |
| Předmět: |
0102 computer and information sciences
02 engineering and technology [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] 01 natural sciences Theoretical Computer Science Combinatorics Set (abstract data type) Exponential growth FOS: Mathematics 0202 electrical engineering electronic engineering information engineering Mathematics - Combinatorics Discrete Mathematics and Combinatorics Order (group theory) ComputingMilieux_MISCELLANEOUS Independence (probability theory) Mathematics Discrete mathematics Exponential independence 020206 networking & telecommunications Exponential function Vertex (geometry) Exponential domination 010201 computation theory & mathematics Independent set Combinatorics (math.CO) Tree (set theory) |
| Zdroj: | Discrete Mathematics Discrete Mathematics, Elsevier, 2021, 344 (8), pp.#112439. ⟨10.1016/j.disc.2021.112439⟩ |
| ISSN: | 0012-365X |
| DOI: | 10.1016/j.disc.2021.112439 |
| Popis: | A set S of vertices of a graph G is exponentially independent if, for every vertex u in S, ∑ v ∈ S ∖ { 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 α 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 Ω ( 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 . |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect