Egalitarian Edge Orderings of Complete Graphs
Autor: | Charles J. Colbourn |
---|---|
Rok vydání: | 2021 |
Předmět: |
Computer Science::Computer Science and Game Theory
0211 other engineering and technologies Complete graph 021107 urban & regional planning 0102 computer and information sciences 02 engineering and technology Edge (geometry) 01 natural sciences Graph Theoretical Computer Science Vertex (geometry) Combinatorics 010201 computation theory & mathematics Discrete Mathematics and Combinatorics Mathematics |
Zdroj: | Graphs and Combinatorics. 37:1405-1413 |
ISSN: | 1435-5914 0911-0119 |
Popis: | For a consecutive ordering of the edges of a graph $$G=(V,E)$$ , the point sum of a vertex is the sum of the indices of edges incident with that vertex. Motivated by questions of balancing accesses in data placements in the presence of popularity rankings, an edge ordering is egalitarian when all point sums are equal, and almost egalitarian when two point sums differ by at most 1. It is established herein that complete graphs on n vertices admit an egalitarian edge ordering when $$n \equiv 1,2,3 \pmod {4}$$ and $$n \not \in \{3,5\}$$ , or an almost egalitarian edge ordering when $$n \equiv 0 \pmod {4}$$ and $$n \ne 4$$ . |
Databáze: | OpenAIRE |
Externí odkaz: |