✦ LIBER ✦

Average distance in colored graphs

✍ Scribed by Peter Dankelmann; Wayne Goddard; Peter Slater

Publisher: John Wiley and Sons
Year: 2001
Tongue: English
Weight: 143 KB
Volume: 38
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.1020

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

For a graph G where the vertices are colored, the colored distance of G is defined as the sum of the distances between all unordered pairs of vertices having different colors. Then for a fixed supply s of colors, d~s~(G) is defined as the minimum colored distance over all colorings with s. This generalizes the concepts of median and average distance. In this paper we explore bounds on this parameter, especially a natural lower bound and the particular case of balanced 2‐colorings (equal numbers of red and blue). We show that the general problem is NP‐hard but there is a polynomial‐time algorithm for trees. © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 1–17, 2001

📜 SIMILAR VOLUMES

Distance Graphs andT-Coloring

✍ Gerard J Chang; Daphne D.-F Liu; Xuding Zhu 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 126 KB

We discuss relationships among T-colorings of graphs and chromatic numbers, fractional chromatic numbers, and circular chromatic numbers of distance graphs. We first prove that for any finite integral set T that contains 0, the asymptotic T-coloring ratio R(T ) is equal to the fractional chromatic n

Minimum Coloring k-Colorable Graphs in P

Minimum Coloring k-Colorable Graphs in Polynomial Average Time

✍ C.R. Subramanian 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 137 KB

We present algorithms for minimum G -coloring k-colorable graphs drawn from random and semi-random models. In both models, an adversary initially splits Ž . the vertices into k color classes V , . . . , V of sizes ⍀ n each. In the first model,

The average Steiner distance of a graph

✍ Dankelmann, Peter; Oellermann, Ortrud R.; Swart, Henda C. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 384 KB 👁 2 views

The average distance p(G) of a graph G is the average among the distances between all pairs of vertices in G. For n 2 2, the average Steiner n-distance ,4G) of a connected graph G is the average Steiner distance over all sets of n vertices in G. It is shown that for a connected weighted graph G, pu,

Pattern Periodic Coloring of Distance Gr

Pattern Periodic Coloring of Distance Graphs

✍ Xuding Zhu 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 250 KB

Suppose D is a subset of Z. The distance graph G(Z, D) with distance set D is the graph with vertex set Z and two vertices x, y are adjacent if |x& y| # D. We introduce a coloring method for distance graphs, the pattern periodic coloring, and we shall compare this method with other general coloring

Domination in colored complete graphs

✍ P. Erdös; R. Faudree; A. Gyárfás; R. H. Schelp 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 251 KB

Properly colored hamilton cycles in edge

Properly colored hamilton cycles in edge-colored complete graphs

✍ N. Alon; G. Gutin 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 156 KB 👁 3 views

It is shown that, for ⑀ ) 0 and n ) n ⑀ , any complete graph K on n vertices 0 ' Ž . whose edges are colored so that no vertex is incident with more than 1 y 1r 2 y ⑀ n edges of the same color contains a Hamilton cycle in which adjacent edges have distinct colors. Moreover, for every k between 3 and