Originators: Ermelinda DeLaViña and Graffiti.ps (presented by Douglas West - REGS 2008)
Definitions: The connected domination number, written γc(G), is the minimum number of vertices in a dominating set that induces a connected subgraph in G. The local independence number, written μ(G), is the maximum number of edges in an induced subgraph that is a star; equivalently, it is the maximum size of an independent set contained in a vertex neighborhood. Also, α(G) denotes the maximum size of an independent set of vertices in G, and b(G) denotes the maximum number of vertices in an induced subgraph of G that is bipartite. Let D(G) denote the average distance in G, that is, the sum of the distances between vertices, divided by the number (2n) of such distances.
Background: Among hundreds of conjectures made by the computer program Graffiti, Conjecture #2 was the famous conjecture that D(G)≤α(G), proved by Chung [C] and more recently by Dankelmann [D]. Conjecture #747 by Graffiti (1992) is a strengthening of this inequality to D(G)≤ ½b(G). Related to this inequality is the following conjecture, posed by the successor program Graffiti.ps.
Conjecture: If G is a graph, then b(G)≥γc(G)+μ(G)-1.
Comments: It is easy to show that b(G)≥γc(G)+1, which is sharp for odd cycles, and this leads to D(G)<½b(G)+1. DeLaViña and Waller [DW] proved that b(G)≥γc(G)+⌈½(μ(G)-1)⌉, which leads to D(G)<½(b(G)+1) and when μ(G)≥5 to the desired D(G)≤ b(G)/2. If the full conjecture above is true, it would also be interesting to know for which graphs it is sharp.
References:
[C] F. R. K. Chung, The average distance and the independence number. J. Graph
Theory 12 (1988), no. 2, 229--235.
[D] P. Dankelmann, Average distance and independence number. 2nd Twente
Workshop on Graphs and Combinatorial Optimization (Enschede, 1991). Discrete
Appl. Math. 51 (1994), no. 1-2, 75--83.
[DW] E. DeLaViña and B. Waller, Spanning trees with many leaves and average
distance.