Skip to content
DraconiticResearch
Search Sources API
203,948 studies31 sourcesUpdated 21 min ago
PreprintCC BY 4.0arXiv

Constructing two completely independent spanning trees in dual-cubes

  • Mohammed Lalou
  • Nader Mbarek
  • Abdallah Skender
  • Olivier Togni
Open at sourcePDFDOICite

Abstract

In this paper, we prove the existence of two completely independent spanning trees in the n-dimensional dual-cube Fn, a variant of the hypercube, for every n ≥ 5. To this end, we use the hypercube structure of the clusters of Fn to extend the construction of CIST from the (n−1)-dimensional hypercube to the dual-cube. In addition, we provide a recursive algorithm that builds the two trees while improving their diameters. Finally, we propose a conjecture regarding the existence of k completely independent spanning trees in the dual-cube.

Related

  1. On Hypergraph Colorings and Completely Independent Spanning Trees in Chordal Graphs
    Mohammed Lalou, Nader Mbarek, Abdallah Skender +1
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. Extremal Spanning Trees of Random Marked Graphs with Independent Edge Weights
    Ghurumuruhan Ganesan
    arXivPreprintCC BY 4.0Full textProbabilityarXiv
  3. Spectral radius and edge-disjoint spanning trees of graphs with edge connectivity
    Jia Wei, Muhuo Liu, Zhifu You +1
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. A quadratic ancestor inequality for spanning trees
    Gefei Cai
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsMathematical physicsarXiv
  5. Spanning k-trees and the colorful Carathéodory theorem
    Mikhail Bludov, Alexander Polyanskii
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{lalou2026constructing,
  title = {{Constructing two completely independent spanning trees in dual-cubes}},
  author = {Mohammed Lalou and Nader Mbarek and Abdallah Skender and Olivier Togni},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2607.25917},
  eprint = {2607.25917},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2607.25917},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Constructing two completely independent spanning trees in dual-cubes
AU  - Mohammed Lalou
AU  - Nader Mbarek
AU  - Abdallah Skender
AU  - Olivier Togni
PY  - 2026
DA  - 2026/09/21
PB  - arXiv
DO  - 10.48550/arxiv.2607.25917
UR  - https://arxiv.org/abs/2607.25917
AB  - In this paper, we prove the existence of two completely independent spanning trees in the n-dimensional dual-cube F_n, a variant of the hypercube, for every n ≥ 5. To this end, we use the hypercube structure of the clusters of F_n to extend the construction of CIST from the (n−1)-dimensional hypercube to the dual-cube. In addition, we provide a recursive algorithm that builds the two trees while improving their diameters. Finally, we propose a conjecture regarding the existence of k completely independent spanning trees in the dual-cube.
ER  -