2019/03/24 by Soogang Eoh, Eoh, Soogang, Suh-Ryung Kim +1
Computer Science · Mathematics · #Advanced Algebra and Logic #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #math.CO
paper · pdf · doi:10.48550/arxiv.1903.09933
arxiv created 2019/03/24 · openalex publication_date 2019/03/24 · arxiv updated 2019/03/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we introduce the notion of the weak majority dimension of a digraph which is well-defined for any digraph. We first study properties shared by the weak dimension of a digraph and show that a weak majority dimension of a digraph can be arbitrarily large. Then we present a complete characterization of digraphs of weak majority dimension 0 and 1, respectively, and show that every digraph with weak majority dimension at most two is transitive. Finally, we compute the weak majority dimensions of directed paths and directed cycles and pose open problems.