Strengthening the Murty–Simon conjecture on diameter 2 critical graphs

A graph is diameter-2-critical if its diameter is 2 but the removal of any edge increases the diameter. A well-studied conjecture, known as the Murty–Simon conjecture, states that any diameter-2-critical graph of order $n$ has at most $?n^2∕4?$ edges, with equality if and only if $G$ is a balanced complete bipartite graph. Many partial results about this conjecture have been obtained, in particular it is known to hold for all sufficiently large graphs, for all triangle-free graphs, and for all graphs with a dominating edge. In this paper, we discuss ways in which this conjecture can be strengthened. Extending previous conjectures in this direction, we conjecture that, when we exclude the class of complete bipartite graphs and one particular graph, the maximum number of edges of a diameter-2-critical graph is at most $?{(n?1)}^2∕4?+1$. The family of extremal examples is conjectured to consist of certain twin-expansions of the 5-cycle (with the exception of a set of thirteen special small graphs). Our main result is a step towards our conjecture: we show that the Murty–Simon bound is not tight for non-bipartite diameter-2-critical graphs that have a dominating edge, as they have at most $?n^2∕4??2$ edges. Along the way, we give a shorter proof of the Murty–Simon conjecture for this class of graphs, and stronger bounds for more specific cases. We also characterize diameter-2-critical graphs of order $n$ with maximum degree $n?2$: they form an interesting family of graphs with a dominating edge and $2n?4$ edges.     

The generalized hierarchical product of graphs

A generalization of both the hierarchical product and the Cartesian product of graphs is introduced and some of its properties are studied. We call it the generalized hierarchical product. In fact, the obtained graphs turn out to be subgraphs of the Cartesian product of the corresponding factors. Thus, some well-known properties of this product, such as a good connectivity, reduced mean distance, radius and diameter, simple routing algorithms and some optimal communication protocols, are inherited by the generalized hierarchical product. Besides some of these properties, in this paper we study the spectrum, the existence of Hamiltonian cycles, the chromatic number and index, and the connectivity of the generalized hierarchical product.     

On the girth and diameter of generalized Johnson graphs

Let $v>k>i$ be non-negative integers. The generalized Johnson graph, $J(v,k,i)$, is the graph whose vertices are the $k$-subsets of a $v$-set, where vertices $A$ and $B$ are adjacent whenever $|A\cap B|=i$. In this article, we derive general formulas for the girth and diameter of $J(v,k,i)$. Additionally, we provide a formula for the distance between any two vertices $A$ and $B$ in terms of the cardinality of their intersection.     

Diameter bounds and recursive properties of Full-Flag Johnson graphs

The Johnson graphs $J(n,k)$ are a well-known family of combinatorial graphs whose applications and generalizations have been studied extensively in the literature. In this paper, we present a new variant of the family of Johnson graphs, the Full-Flag Johnson graphs, and discuss their combinatorial properties. We show that the Full-Flag Johnson graphs are Cayley graphs on $S_n$ generated by certain well-known classes of permutations and that they are in fact generalizations of permutahedra. We prove a tight $\Theta (n^2∕k^2)$ bound for the diameter of the Full-Flag Johnson graph FJ$(n,k)$ and establish recursive relations between FJ$(n,k)$ and the lower-order Full-Flag Johnson graphs FJ$(n?1,k)$ and FJ$(n?1,k?1)$. We apply this recursive structure to partially compute the spectrum of permutahedra.     

柠檬酸根辅助多元醇法制备直径和磁性可控的Fe_3O_4亚微球

以柠檬酸三钠作辅助剂,用多元醇溶剂热还原法制备了纳米晶粒和微球直径可控的、单分散的超顺磁Fe3O4亚微球.发现与铁原子有强亲和力的柠檬酸根能有效吸附在还原产生的初始Fe3O4纳米粒子表面,阻碍其晶粒生长和影响其静电排斥力的大小,从而能在较大范围内调控最终产物Fe3O4亚微球的直径和饱和磁化强度.改变柠檬酸根或铁盐浓度不但可以调控初始Fe3O4纳米粒子的粒径,而且可以在220-550nm范围内调控单分散Fe3O4亚微球的直径,从而得到粒径均一的超顺磁Fe3O4亚微球.     

A new class of transitive graphs

Let n and k be integers with n≥k≥0. This paper presents a new class of graphs H(n,k), which contains hypercubes and some well-known graphs, such as Johnson graphs, Kneser graphs and Petersen graph, as its subgraphs. The authors present some results of algebraic and topological properties of H(n,k). For example, H(n,k) is a Cayley graph, the automorphism group of H(n,k) contains a subgroup of order 2ⁿn! and H(n,k) has a maximal connectivity and is hamiltonian if k is odd; it consists of two isomorphic connected components if k is even. Moreover, the diameter of H(n,k) is determined if k is odd.