On betweenness-uniform graphs

The betweenness centrality of a vertex of a graph is the fraction of shortest paths between all pairs of vertices passing through that vertex. In this paper, we study properties and constructions of graphs whose vertices have the same value of betweenness centrality (betweenness-uniform graphs); we show that this property holds for distanceregular graphs (which include strongly regular graphs) and various graphs obtained by graph cloning and local join operation. In addition, we show that, for sufficiently large n, there are superpolynomially many betweenness-uniform graphs on n vertices, and explore the structure of betweenness-uniform graphs having a universal or sub-universal vertex.     

Spatial bi-stacked central configurations formed by two dual regular polyhedra

In this paper we prove the existence of two new families of spatial stacked central configurations, one consisting of eight equal masses on the vertices of a cube and six equal masses on the vertices of a regular octahedron, and the other one consisting of twenty masses at the vertices of a regular dodecahedron and twelve masses at the vertices of a regular icosahedron. The masses on the two different polyhedra are in general different. We note that the cube and the octahedron, the dodecahedron and the icosahedron are dual regular polyhedra. The tetrahedron is itself dual. There are also spatial stacked central configurations formed by two tetrahedra, one and its dual.     

The geometry of t‐spreads in k‐walk‐regular graphs

A graph is walk‐regular if the number of closed walks of length ? rooted at a given vertex is a constant through all the vertices for all ?. For a walk‐regular graph G with d+1 different eigenvalues and spectrally maximum diameter D=d, we study the geometry of its d‐spreads, that is, the sets of vertices which are mutually at distance d. When these vertices are projected onto an eigenspace of its adjacency matrix, we show that they form a simplex (or tetrahedron in a three‐dimensional case) and we compute its parameters. Moreover, the results are generalized to the case of k‐walk‐regular graphs, a family which includes both walk‐regular and distance‐regular graphs, and their t‐spreads or vertices at distance t from each other. © 2009 Wiley Periodicals, Inc. J Graph Theory 64:312–322, 2010     

Regular pseudo-median graphs

A graph is pseudo-median if for every triple u, v, w of vertices there exists either a unique vertex between each pair of them (if their mutual distances sum up to an even number) or a unique triangle whose edges lie between the three pairs of u, v, w, respectively (if the distance sum is odd). We show that a finite pseudo-median graph is regular if and only if it is the Cartesian product of a hypercube with either a complete graph or a hyper-octahedron. Every self-map of a pseudo-median graph that preserves or collapses edges has an invariant regular pseudo-median subgraph. Furthermore, the set of all vertices minimizing the total distance to the vertices of a pseudo-median graph induces a regular pseudo-median subgraph.     

A Polynomial Time Approximation Scheme for Optimal Product-Requirement Communication Spanning Trees

Given an undirected graph with nonnegative edge lengths and nonnegative vertex weights, the routing requirement of a pair of vertices is assumed to be the product of their weights. The routing cost for a pair of vertices on a given spanning tree is defined as the length of the path between them multiplied by their routing requirement. The optimal product-requirement communication spanning tree is the spanning tree with minimum total routing cost summed over all pairs of vertices. This problem arises in network design and computational biology. For the special case that all vertex weights are identical, it has been shown that the problem is NP-hard and that there is a polynomial time approximation scheme for it. In this paper we show that the generalized problem also admits a polynomial time approximation scheme.     

Four icosahedra can meet at a point

What is the maximal number of nonoverlapping copies of a regular polyhedron ∏ that can share a common vertex? The answer is shown to be 4 if ∏ is an icosahedron or dodecahedron, and is conjectured to be 7 for an octahedron and 20 for a tetrahedron. (For a cube the answer is trivially 8.)     

Vertex-faithful regular polyhedra

We study the abstract regular polyhedra with automorphism groups that act faithfully on their vertices, and show that each non-flat abstract regular polyhedron covers a “vertex-faithful” polyhedron with the same number of vertices. We then use this result and earlier work on flat polyhedra to study abstract regular polyhedra based on the size of their vertex set. In particular, we classify all regular polyhedra where the number of vertices is prime or twice a prime. We also construct the smallest regular polyhedra with a prime squared number of vertices.     

Bounds on Special Subsets in Graphs, Eigenvalues and Association Schemes

We give a bound on the sizes of two sets of vertices at a given minimum distance in a graph in terms of polynomials and the Laplace spectrum of the graph. We obtain explicit bounds on the number of vertices at maximal distance and distance two from a given vertex, and on the size of two equally large sets at maximal distance. For graphs with four eigenvalues we find bounds on the number of vertices that are not adjacent to a given vertex and that have µ common neighbours with that vertex. Furthermore we find that the regular graphs for which the bounds are tight come from association schemes.     

Graphs which are locally a cube

We prove that there are exactly two connected graphs which are locally a cube: a graph on 15 vertices which is the complement of the (3×5)-grid and a graph on 24 vertices which is the 1-skeleton of a certain 4-dimensional regular polytope called the 24-cell.     

Notes on the betweenness centrality of a graph

The betweenness centrality of a vertex of a graph is the portion of the shortest paths between all pairs of vertices passing through a given vertex. We study upper bounds for this invariant and its relations to the diameter and average distance of a graph.     

Random walks on graphs

In this paper the following Markov chains are considered: the state space is the set of vertices of a connected graph, and for each vertex the transition is always to an adjacent vertex, such that each of the adjacent vertices has the same probability. Detailed results are given on the expectation of recurrence times, of first-entrance times, and of symmetrized first-entrance times (called commuting times). The problem of characterizing all connected graphs for which the commuting time is constant over all pairs of adjacent vertices is solved almost completely.     

一类三圈图的Wiener指数

图G的Wiener指数是指图G中所有顶点对间的距离之和,即W（G）=∑dc（u,u）,{u,u}CG其中de（u,u）表示G中顶点u,u之间的距离.三圈图是指边数与顶点数之差等于2的连通图,任意两个圈至多只有一个公共点的三圈图记为T_n~3.研究了三圈图T_n~3的Wiener指数,给出了其具有最小、次小Wiener指数的图结构.     

On simplices in diameter graphs in ℝ4

Agraph G is a diameter graph in ?^d if its vertex set is a finite subset in ?^d of diameter 1 and edges join pairs of vertices a unit distance apart. It is shown that if a diameter graph G in ?⁴ contains the complete subgraph K on five vertices, then any triangle in G shares a vertex with K. The geometric interpretation of this statement is as follows. Given any regular unit simplex on five vertices and any regular unit triangle in ?⁴, then either the simplex and the triangle have a common vertex or the diameter of the union of their vertex sets is strictly greater than 1.

     

A new infinite series of regular uniformly geodetic code graphs

We construct vertex-transitive graphs Γ, regular of valency k=n²+n+1 on vertices, with integral spectrum, possessing a distinguished complete matching such that contracting the edges of this matching yields the Johnson graph J(2n, n) (of valency n²). These graphs are uniformly geodetic in the sense of Cook and Pryce (1983) (F-geodetic in the sense of Ceccharini and Sappa (1986)), i.e., the number of geodesics between any two vertices only depends on their distance (and equals 4 when this distance is two). They are counterexamples to Theorem 3.15.1 of [1], and we show that there are no other counterexamples.     

Growth Series and Random Walks on Some Hyperbolic Graphs

 Consider the tessellation of the hyperbolic plane by m-gons, ℓ per vertex. In its 1-skeleton, we compute the growth series of vertices, geodesics, tuples of geodesics with common extremities. We also introduce and enumerate holly trees, a family of proper loops in these graphs. We then apply Grigorchuk’s result relating cogrowth and random walks to obtain lower estimates on the spectral radius of the Markov operator associated with a symmetric random walk on these graphs.     

The product of the distances of a point inside a regular polytope to its vertices

We show that the maximum of the product of the distances from a point inside an n-dimensional regular simplex, cross-polytope or cube to the vertices is attained at the midpoint of an edge for small n, but is attained at symmetrically placed pairs on an edge for sufficiently high dimensions. We also examine the problem for regular polygons and general triangles in the plane. Murray Klamkin passed away on August 15, 2004. He was Professor of Mathematics at the University of Alberta, Edmonton, Alberta, Canada.     

Regular simple geodesic loops on a tetrahedron

A regular simple geodesic loop on a tetrahedron is a simple geodesic loop which does not pass through any vertex of the tetrahedron. It is evident that such loops meet each face of the tetrahedron. Among these loops, the minimal loops are those which meet each face exactly once. Necessary and sufficient conditions for the existence of minimal loops are obtained. These conditions fall naturally into two categories, conditions in the first category being called coherence conditions and conditions in the second category being called separation conditions. It is shown that for the existence of three distinct minimal loops through any point on the face of a tetrahedron it is necessary and sufficient that the tetrahedron be isosceles, which, in turn, amounts to the tetrahedron satisfying three coherence conditions. All other regular simple geodesic loops on an isosceles tetrahedron are then classified. Finally, coherence conditions for the existence of similar loops on an arbitrary tetrahedron are found.     

Sources and Sinks in Comparability Graphs

We prove that a subset S of vertices of a comparability graph G is a source set if and only if each vertex of S is a source and there is no odd induced path in G between two vertices of S. We also characterize pairs of subsets corresponding to sources and sinks, respectively. Finally, an application to interval graphs is obtained.     

Special Eccentric Vertices for the Class of Chordal Graphs and Related Classes

A vertex is simplicial if the vertices of its neighborhood are pairwise adjacent. It is known that, for every vertex v of a chordal graph, there exists a simplicial vertex among the vertices at maximum distance from v. Here we prove similar properties in other classes of graphs related to that of chordal graphs. Those properties will not be in terms of simplicial vertices, but in terms of other types of vertices that are used to characterize those classes.