连通的三重Kn-残差图

Erds P,Harary F和Klawe M研究了Kn-残差图,并对连通的m-Kn-残差图提出了一些结论和猜想．利用容斥原理以及集合的运算性质等方法,研究了连通的3-Kn-残差图,得到当顶点最小度为n时,3-Kn-残差图最小阶的计算公式以及相应的唯一极图．当n=2时,得到最小阶为ll以及相应的极图;当n=3时,得到最小阶为20并找到两个不同构的极图,不满足Erdos等提出的结论;当n=4时,得到最小阶为22及相应的极图;当n=8时,可以找到两个不同构的3-Kn-残差图,不满足Erdos等提出的结论;最后证明了当n=9,10时,最小阶分别为48和52以及相应的唯一极图,验证了Erdos等在文献（Residually-complete graphs[J]．Annals of Discrete Mathematics,1980,6：117．123）中提出的结论．     

Characterization of maximum critically 2-connected graphs

A graph G is critically 2-connected if G is 2-connected but, for any point p of G, G — p is not 2-connected. Critically 2-connected graphs on n points that have the maximum number of lines are characterized and shown to be unique for n ? 3, n ≠ 11.     

On perfect and multiply perfect numbers

Summary Denote by P(x) the number of integers n≤x satisfying σ(n)≡0 (mod n), and by P ₂ (x) the number of integers n ≤ x satisfying σ(n)=2n. The author proves that P(x)<x ^3/4+ɛ and P ₂ (x)<x ^(1−c)/2 for a certain c>0.     

线团-收敛图

一个图的线团图就是这个图的线图的团图。对于自然数n，一个图被称为n-线团－收敛的，如果它的n次线团图同构于一个固定的图。否则称之为发散的。本刻画了线团－收敛图与发散图，给出一个线团－收敛图的构造方法，并且，讨论了线团－收敛图的线团－收敛指数。     

On clique-critical graphs

A graph G is clique-critical if G and G?x have different clique-graphs for all vertices x of G. For any graph H, there is at most a finite number of different clique-critical graphs G such that H is the clique-graph of G. Upper and lower bounds for the number of vertices of the cliques of the critical graphs are obtained.     

On hamiltonian-connected graphs

One of the most fundamental results concerning paths in graphs is due to Ore: In a graph G, if deg x + deg y ≧ |V(G)| + 1 for all pairs of nonadjacent vertices x, y ? V(G), then G is hamiltonian-connected. We generalize this result using set degrees. That is, for S ? V(G), let deg S = |_x?S N(x)|, where N(x) = {v|xv ? E(G)} is the neighborhood of x. In particular we show: In a 3-connected graph G, if deg S₁ + deg S₂ ≧ |V(G)| + 1 for each pair of distinct 2-sets of vertices S₁, S₂ ? V(G), then G is hamiltonian-connected. Several corollaries and related results are also discussed.     

On s-hamiltonian line graphs of claw-free graphs

For an integer $s\ge 0$, a graph $G$ is $s$-hamiltonian if for any vertex subset $S?V\left(G\right)$ with $\left|S\right|\le s$, $G?S$ is hamiltonian, and $G$ is $s$-hamiltonian connected if for any vertex subset $S?V\left(G\right)$ with $\left|S\right|\le s$, $G?S$ is hamiltonian connected. Thomassen in 1984 conjectured that every 4-connected line graph is hamiltonian (see Thomassen, 1986), and Ku?zel and Xiong in 2004 conjectured that every 4-connected line graph is hamiltonian connected (see Ryjá?ek and Vrána, 2011). In Broersma and Veldman (1987), Broersma and Veldman raised the characterization problem of $s$-hamiltonian line graphs. In Lai and Shao (2013), it is conjectured that for $s\ge 2$, a line graph $L\left(G\right)$ is $s$-hamiltonian if and only if $L\left(G\right)$ is $(s+2)$-connected. In this paper we prove the following.(i) For an integer $s\ge 2$, the line graph $L\left(G\right)$ of a claw-free graph $G$ is $s$-hamiltonian if and only if $L\left(G\right)$ is $(s+2)$-connected.(ii) The line graph $L\left(G\right)$ of a claw-free graph $G$ is 1-hamiltonian connected if and only if $L\left(G\right)$ is 4-connected.     

On unretractive graphs

The present paper proves necessary and sufficient conditions for both lexicographic products and arbitrary graphs to be unretractive. The paper also proves that the automorphism group of a lexicographic product of graphs is isomorphic to a wreath product of a monoid with a small category.     

On unimodular graphs

We study graphs whose adjacency matrices have determinant equal to 1 or −1, and characterize certain subclasses of these graphs. Graphs whose adjacency matrices are totally unimodular are also characterized. For bipartite graphs having a unique perfect matching, we provide a formula for the inverse of the corresponding adjacency matrix, and address the problem of when that inverse is diagonally similar to a nonnegative matrix. Special attention is paid to the case that such a graph is unicyclic.     

On cover-structure graphs

Motivated by a problem in communication complexity, we study cover-structure graphs (cs-graphs), defined as intersection graphs of maximal monochromatic rectangles in a matrix. We show that not every graph is a cs-graph. Especially, squares and odd holes are not cs-graphs.It is natural to look at graphs (beautiful graphs) having the property that each induced subgraph is a cs-graph. They form a new class of Berge graphs. We make progress towards their characterization by showing that every square-free bipartite graph is beautiful, and that beautiful line graphs of square-free bipartite graphs are just Path-or-Even-Cycle-of-Cliques graphs.     

On replete graphs

A graph G is k-clique replete if G has clique number k and every elementary homomorphism of G has clique number greater than k. Results on the order of k-clique replete graphs are presented, and bounds for the minimum degree and the maximum degree of such graphs are discussed.     

On factor-invariant graphs

We classify trivalent vertex-transitive graphs whose edge sets have a partition into a Hamilton cycle and a 1-factor that is invariant under the action of the full automorphism group.     

On time graphs

For n points on the real line, joining each pair of points such that their difference is less than a certain positive constant, we have a time graph. In this paper we characterize time graphs and enumerate them.     

On hypohamiltonian graphs

Herz, Duby and Vigué [9] conjectured that every hypohamiltonian graph has girth 5. In the present note hypohamiltonian graphs of girth 3 and 4 are described. Also two conjectures on hypohamiltonian graphs made by Bondy and Chvátal, respectively, are disproved.     

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.     

On Gorenstein graphs

We classify all Gorenstein claw-free graphs. Moreover, we provide a new way to construct a Gorenstein graph from another one.