The average degree of a subcubic edge-chromatic critical graph

A graph is here called 3- critical if , and for every edge of . The 3-critical graphs include (the Petersen graph with a vertex deleted), and subcubic graphs that are Hajós joins of copies of . Building on a recent paper of Cranston and Rabern, it is proved here that if is 3-critical and not nor a Hajós join of two copies of , then has average degree at least ; this bound is sharp, as it is the average degree of a Hajós join of three copies of .     

Mean distance in a graph

The average or mean of the distances between vertices in a connected graph Γ, μ(Γ), is a natural measure of the compactness of the graph. In this paper we compute bounds for μ(Γ) in terms of the number of vertices in Γ and the diameter of Γ. We prove a formula for computing μ(Γ) when Γ is a tree which is particularly useful when Γ has a high degree of symmetry. Finally, we present algorithms for μ(Γ) which are amenable to computer implementation.     

On the average genus of a graph

Not all rational numbers are possibilities for the average genus of an individual graph. The smallest such numbers are determined, and varied examples are constructed to demonstrate that a single value of average genus can be shared by arbitrarily many different graphs. It is proved that the number 1 is a limit point of the set of possible values for average genus and that the complete graph K₄ is the only 3-connected graph whose average genus is less than 1.     

Steiner symmetrals and their distance from a ball

It is known that given any convex bodyK ⊂ ℝ ⁿ there is a sequence of suitable iterated Steiner symmetrizations ofK that converges, in the Hausdorff metric, to a ball of the same volume. Hadwiger and, more recently, Bourgain, Lindenstrauss and Milman have given estimates from above of the numberN of symmetrizations necessary to transformK into a body whose distance from the equivalent ball is less than an arbitrary positive constant. In this paper we will exhibit some examples of convex bodies which are “hard to make spherical”. For instance, for any choice of positive integersn≥2 andm, we construct ann-dimensional convex body with the property that any sequence ofm symmetrizations does not decrease its distance from the ball. A consequence of these constructions are some lower bounds on the numberN.     

Structure for a graph with average genus

In [2], Chen et al. showed that the average genus for a graph of maximum degree at most 3 is at least 1/2 its maximum genus. In this paper, the structure for a graph of maximum degree at most 3 with average genus equal to 1/2 its maximum genus is described. Furthermore, LetH be a subgraph ofG and γ_avg(G) = γ_avg(H). It’s shown thatG can be obtained by a series operations of type I and II onH.     

The center and the distance center of a ptolemaic graph

The points of a distance center in a Ptolemaic graph G induce a complete subgraph of G, and the points of a center in a chordal graph constitute a convex.     

On the degree distance of a graph

If G is a connected graph with vertex set V, then the degree distance of G, D^′(G), is defined as , where degw is the degree of vertex w, and d(u,v) denotes the distance between u and v. We prove the asymptotically sharp upper bound for graphs of order n and diameter d. As a corollary we obtain the bound for graphs of order n. This essentially proves a conjecture by Tomescu [I. Tomescu, Some extremal properties of the degree distance of a graph, Discrete Appl. Math. (98) (1999) 159-163].     

The average distance and the independence number

We prove that in every connected graph the independence number is at least as large as the average distance between vertices.     

On the dimension to represent a graph by a unit distance graph

It is proved that if a graphG has maximum degreed, then its vertices can be represented by distinct unit vectors inR ^2d so that two vectors are orthogonal if and only if the corresponding vertices are adjacent. As a corollary it follows that if a graph has maximum degreed, then it is isomorphic to a unit distance graph inR ^2d.     

On the distance matrix of a directed graph

In this note, we show how the determinant of the distance matrix D(G) of a weighted, directed graph G can be explicitly expressed in terms of the corresponding determinants for the (strong) blocks G_i of G. In particular, when cof D(G), the sum of the cofactors of D(G), does not vanish, we have the very attractive formula .     

On the distance function of a connected graph

An axiomatic characterization of the distance function of a connected graph is given in this note. The triangle inequality is not contained in this characterization.     

Comparison of formulations and a heuristic for packing Steiner trees in a graph

In this paper, we consider the problem of packing Steiner trees in a graph. This problem arises during the global routing phase of circuit layout design. We consider various integer programming formulations and rank them according to lower bounds they provide as LP-relaxations. We discuss a solution procedure to obtain both lower and upper bounds using one of the LP-relaxations. Computational results to test the effectiveness of our procedures are provided.     

On the least distance eigenvalue of a graph

Denote by D(G)=_(di,j)n×n$D(G)={(d_{i,j})}_{n\times n}$ the distance matrix of a connected graph G with n   vertices, where _dij$d_{ij}$ is equal to the distance between vertices _vi$v_i$ and _vj$v_j$ in G  . The least eigenvalue of D(G)$D(G)$ is called the least distance eigenvalue of G  , denoted by _λn${\lambda }_n$. In this paper, we determine all the graphs with _λn∈[−2.383,0]${\lambda }_n\in [-2.383,0]$.