Average distance in graphs and eigenvalues

Brendan McKay gave the following formula relating the average distance between pairs of vertices in a tree T and the eigenvalues of its Laplacian:

     

Coloring of distance graphs with intervals as distance sets

Let D be a set of positive integers. The distance graph G(Z,D) with distance set D is the graph with vertex set Z in which two vertices x,y are adjacent if and only if |x−y|D. The fractional chromatic number, the chromatic number, and the circular chromatic number of G(Z,D) for various D have been extensively studied recently. In this paper, we investigate the fractional chromatic number, the chromatic number, and the circular chromatic number of the distance graphs with the distance sets of the form D_m,[k,k^′]={1,2,…,m}−{k,k+1,…,k^′}, where m, k, and k^′ are natural numbers with m≥k^′≥k. In particular, we completely determine the chromatic number of G(Z,D_m,[2,k^′]) for arbitrary m, and k^′.     

Orientation distance graphs

For two nonisomorphic orientations D and D′ of a graph G, the orientation distance d_o(D,D′) between D and D′ is the minimum number of arcs of D whose directions must be reversed to produce an orientation isomorphic to D′. The orientation distance graph 𝒟_o(G) of G has the set 𝒪(G) of pairwise nonisomorphic orientations of G as its vertex set and two vertices D and D′ of 𝒟₀(G) are adjacent if and only if d_o(D,D′) = 1. For a nonempty subset S of 𝒪(G), the orientation distance graph 𝒟₀(S) of S is the induced subgraph 〈S〉 of 𝒟_o(G). A graph H is an orientation distance graph if there exists a graph G and a set S⊆ 𝒪(G) such that 𝒟_o(S) is isomorphic to H. In this case, H is said to be an orientation distance graph with respect to G. This paper deals primarily with orientation distance graphs with respect to paths. For every integer n ≥ 4, it is shown that 𝒟_o(P_n) is Hamiltonian if and only if n is even. Also, the orientation distance graph of a path of odd order is bipartite. Furthermore, every tree is an orientation distance graph with respect to some path, as is every cycle, and for n ≥ 3 the clique number of 𝒟_o(P_n) is 2 if n is odd and is 3 otherwise. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 230–241, 2001     

Colouring prime distance graphs

Four colours are necessary and sufficient to colour all the integers so that any two with difference equal to a prime have different colours. We investigate the corresponding problem when the setD of prescribed differences is a proper subset of the primes. In particular, we prove that ifD contains {2, 3} and also contains a pair of twin primes (one of which may be 3), then four colours are necessary. Numerous results regarding periodic colourings are also obtained. However, the problem of characterizing those setsD which necessitate four colours remains open.     

Boolean distance for graphs

The boolean distance between two points x and y of a connected graph G is defined as the set of all points on all paths joining x and y in G (Ø if x = y). It is determined in terms of the block-cutpoint graph of G, and shown to satisfy the triangle inequality b(x,y)? b(x, z)∪b(z,y). We denote by B(G) the collection of distinct boolean distances of G and by M(G) the multiset of the distances together with the number of occurrences of each of them. Then $\text{B(G)}\text{= 1+(}{}^{\mathrm{b+1}}{}_2\text{)}$ where b is the number of blocks of G. A combinatorial characterization is given for B(T) where T is a tree. Finally, G is reconstructible from M(G) if and only if every block of G is a line or a triangle.     

On embedding of finite distance graphs with large chromatic number in random graphs

The paper studies the problem indicated in the title, which arises in connection with the well-known Nelson–Erdös–Hadwiger problem of finding the chromatic number of the Euclidean space.     

Average case analysis of DJ graphs

Sreedhar et al. [V.C. Sreedhar, G.R. Gao, Y.-F. Lee, A new framework for elimination-based data flow analysis using DJ graphs, ACM Trans. Program. Lang. Syst. 20 (2) (1998) 388–435; V.C. Sreedhar, Efficient program analysis using DJ graphs, PhD thesis, School of Computer Science, McGill University, Montréal, Québec, Canada, 1995] have presented an elimination-based algorithm to solve data flow problems. A thorough analysis of the algorithm shows that the worst-case performance is at least quadratic in the number of nodes of the underlying graph. In contrast, Sreedhar reports a linear time behavior based on some practical applications.

In this paper we prove that for goto-free programs, the average case behavior is indeed linear. As a byproduct our result also applies to the average size of the so-called dominance frontier.

A thorough average case analysis based on a graph grammar is performed by studying properties of the j-edges in DJ graphs. It appears that this is the first time that a graph grammar is used in order to analyze an algorithm. The average linear time of the algorithm is obtained by classic techniques in the analysis of algorithms and data structures such as singularity analysis of generating functions and transfer lemmas.     

Average degrees of edge-chromatic critical graphs

Let $G$ be a simple graph, and let $\Delta \left(G\right)$, $\overline{d}\left(G\right)$ and ${\chi }^{\prime }\left(G\right)$ denote the maximum degree, the average degree and the chromatic index of $G$, respectively. We called $G$ edge-$\Delta$-critical if ${\chi }^{\prime }\left(G\right)=\Delta \left(G\right)+1$ and ${\chi }^{\prime }\left(H\right)\le \Delta \left(G\right)$ for every proper subgraph $H$ of $G$. Vizing in 1968 conjectured that if $G$ is an edge-$\Delta$-critical graph of order $n$, then $\overline{d}\left(G\right)\ge \Delta \left(G\right)?1+\frac{3}{n}$. We prove that for any edge-$\Delta$-critical graph $G$, $\stackrel{?}{d}\left(G\right)\ge min\left\{\frac{2\sqrt{2}\Delta \left(G\right)?3?\sqrt{2}}{2\sqrt{2}+1},\frac{3\Delta \left(G\right)}{4}?2\right\},$ that is, $\overline{d}\left(G\right)\ge \left\{\begin{array}{cc}\frac{3}{4}\Delta \left(G\right)?2\hfill & \text{if}\Delta \left(G\right)\le 75;\hfill \\ \frac{2\sqrt{2}\Delta \left(G\right)?3?\sqrt{2}}{2\sqrt{2}+1}\approx 0.7388\Delta \left(G\right)?1.153\hfill & \text{if}\Delta \left(G\right)\ge 76.\hfill \end{array}\right.$This result improves the best known bound $\frac{2}{3}(\Delta \left(G\right)+2)$ obtained by Woodall in 2007 for $\Delta \left(G\right)\ge 41$.     

On distance two graphs of upper bound graphs

For a poset P=(X,≤), the upper bound graph (UB-graph) of P is the graph U=(X,E_U), where uv∈E_U if and only if u≠v and there exists m∈X such that u,v≤m. For a graph G, the distance two graph DS₂(G) is the graph with vertex set V(DS₂(G))=V(G) and u,v∈V(DS₂(G)) are adjacent if and only if d_G(u,v)=2. In this paper, we deal with distance two graphs of upper bound graphs. We obtain a characterization of distance two graphs of split upper bound graphs.     

Average distances and distance domination numbers

Let k be a positive integer and G be a simple connected graph with order n. The average distance μ(G) of G is defined to be the average value of distances over all pairs of vertices of G. A subset D of vertices in G is said to be a k-dominating set of G if every vertex of V(G)−D is within distance k from some vertex of D. The minimum cardinality among all k-dominating sets of G is called the k-domination number γ_k(G) of G. In this paper tight upper bounds are established for μ(G), as functions of n, k and γ_k(G), which generalizes the earlier results of Dankelmann [P. Dankelmann, Average distance and domination number, Discrete Appl. Math. 80 (1997) 21-35] for k=1.     

Average eccentricity,k-packing and k-domination in graphs

Let $G$ be a connected graph. The eccentricity $e\left(v\right)$ of a vertex $v$ is the distance from $v$ to a vertex farthest from $v$. The average eccentricity $\mathrm{avec}\left(G\right)$ of $G$ is defined as the average of the eccentricities of the vertices of $G$, i.e., as $\frac{1}{\left|V\right|}{\sum }_{v\in V}e\left(v\right)$, where $V$ is the vertex set of $G$. For $k\in \mathbb{N}$, the $k$-packing number of $G$ is the largest cardinality of a set of vertices of $G$ whose pairwise distance is greater than $k$. A $k$-dominating set of $G$ is a set $S$ of vertices such that every vertex of $G$ is within distance $k$ from some vertex of $S$. The $k$-domination number (connected $k$-domination number) of $G$ is the minimum cardinality of a $k$-dominating set (of a $k$-dominating set that induces a connected subgraph) of $G$. For $k=1$, the $k$-packing number, the $k$-domination number and the connected $k$-domination number are the independence number, the domination number and the connected domination number, respectively. In this paper we present upper bounds on the average eccentricity of graphs in terms of order and either $k$-packing number, $k$-domination number or connected $k$-domination number.