Symmetric Graphs and Flag Graphs

 With any G-symmetric graph Γ admitting a nontrivial G-invariant partition , we may associate a natural “cross-sectional” geometry, namely the 1-design in which for and if and only if α is adjacent to at least one vertex in C, where and is the neighbourhood of B in the quotient graph of Γ with respect to . In a vast number of cases, the dual 1-design of contains no repeated blocks, that is, distinct vertices of B are incident in with distinct subsets of blocks of . The purpose of this paper is to give a general construction of such graphs, and then prove that it produces all of them. In particular, we show that such graphs can be reconstructed from and the induced action of G on . The construction reveals a close connection between such graphs and certain G-point-transitive and G-block-transitive 1-designs. By using this construction we give a characterization of G-symmetric graphs such that there is at most one edge between any two blocks of . This leads to, in a subsequent paper, a construction of G-symmetric graphs such that and each is incident in with vertices of B. The work was supported by a discovery-project grant from the Australian Research Council. Received April 24, 2001; in revised form October 9, 2002 Published online May 9, 2003     

双线性型图与交错型图不是完美图

本文证明了双线性型图与交错型图都不是完美图,从而解决了双线性型图与交错型图的完美图判别问题.     

Collapsible Graphs and Hamiltonicity of Line Graphs

Thomassen conjectured that every 4-connected line graph is Hamiltonian. Chen and Lai (Combinatorics and Graph Theory, vol 95, World Scientific, Singapore, pp 53–69; Conjecture 8.6 of 1995) conjectured that every 3-edge connected and essentially 6-edge connected graph is collapsible. Denote D ₃(G) the set of vertices of degree 3 of graph G. For ${e = uv \in E(G)}$ , define d(e) = d(u) + d(v) ? 2 the edge degree of e, and ${\xi(G) = \min\{d(e) : e \in E(G)\}}$ . Denote by λ ^m (G) the m-restricted edge-connectivity of G. In this paper, we prove that a 3-edge-connected graph with ${\xi(G)\geq7}$ , and ${\lambda^3(G)\geq7}$ is collapsible; a 3-edge-connected simple graph with ${\xi(G)\geq7}$ , and ${\lambda^3(G)\geq6}$ is collapsible; a 3-edge-connected graph with ${\xi(G)\geq6}$ , ${\lambda^2(G)\geq4}$ , and ${\lambda^3(G)\geq6}$ with at most 24 vertices of degree 3 is collapsible; a 3-edge-connected simple graph with ${\xi(G)\geq6}$ , and ${\lambda^3(G)\geq5}$ with at most 24 vertices of degree 3 is collapsible; a 3-edge-connected graph with ${\xi(G)\geq5}$ , and ${\lambda^2(G)\geq4}$ with at most 9 vertices of degree 3 is collapsible. As a corollary, we show that a 4-connected line graph L(G) with minimum degree at least 5 and ${|D_3(G)|\leq9}$ is Hamiltonian.     

原始图与三次图的可圈度

本文综述关于原始图与三次图的可圈度的近期结果并提出一些未解决的问题。     

门槛图与度极大图

证明了门槛图与度极大图是一类图的两种不同说法,同时用图的对角限制极左矩阵刻画这一类图的结构。     

Small Universal Graphs for Bounded-Degree Planar Graphs

For all positive integers N and k, let denote the family of planar graphs on N or fewer vertices, and with maximum degree k. For all positive integers N and k, we construct a -universal graph of size . This construction answers with an explicit construction the previously open question of the existence of such a graph. Received July 8, 1998 RID="*" ID="*" Supported by NSF grant CCR98210-58 and ARO grant DAAH04-96-1-0013.     

Snarks,Hypohamiltonian Graphs and Non-Supereulerian Graphs

A graph G is hypohamiltonian if it is not Hamiltonian but for each \(v\in V(G)\), the graph \(G-v\) is Hamiltonian. A graph is supereulerian if it has a spanning Eulerian subgraph. A graph G is called collapsible if for every even subset \(R\subseteq V(G)\), there is a spanning connected subgraph H of G such that R is the set of vertices of odd degree in H. A graph is reduced if it has no nontrivial collapsible subgraphs. In this note, we first prove that all hypohamiltonian cubic graphs are reduced non-supereulerian graphs. Then we introduce an operation to construct graphs from hypohamiltonian cubic graphs such that the resulting graphs are 3-edge-connected non-supereulerian reduced graphs and cannot be contracted to a snark. This disproves two conjectures, one of which was first posed by Catlin et al. in [Congr. Num. 76:173–181, 1990] and in [J. Combin. Theory, Ser B 66:123–139, 1996], and was posed again by Li et al. in [Acta Math. Sin. English Ser 30(2):291–304, 2014] and by Yang in [Supereulerian graphs, hamiltonicity of graphs and several extremal problems in graphs, Ph. D. Dissertation, Université Paris-Sub, September 27, 2013], respectively, the other one was posed by Yang 2013.     

Perfect Graphs, Partitionable Graphs and Cutsets

We prove a theorem about cutsets in partitionable graphs that generalizes earlier results on amalgams, 2-amalgams and homogeneous pairs. Received December 13, 1999 RID="*" ID="*" This work was supported in part by the Fields Institute for Research in Mathematical Sciences, Toronto, Canada, and by NSF grants DMI-0098427 and DMI-9802773 and ONR grant N00014-97-1-0196.     

Small Drawings of Outerplanar Graphs,Series-Parallel Graphs,and Other Planar Graphs

In this paper, we study small planar drawings of planar graphs. For arbitrary planar graphs, Θ(n ²) is the established upper and lower bound on the worst-case area. A long-standing open problem is to determine for what graphs a smaller area can be achieved. We show here that series-parallel graphs can be drawn in O(n ^3/2) area, and outerplanar graphs can be drawn in O(nlog n) area, but 2-outerplanar graphs and planar graphs of proper pathwidth 3 require Ω(n ²) area. Our drawings are visibility representations, which can be converted to polyline drawings of asymptotically the same area.     

关于紧图和超紧图的几个结果

给出了一些 新的紧图,并对 不是超紧的紧图 作了一些讨论     

Induced-Universal Graphs for Graphs with Bounded Maximum Degree

For a family \(\mathcal {F}\) of graphs, a graph U is induced-universal for \({\mathcal{F}}\) if every graph in \({\mathcal{F}}\) is an induced subgraph of U. We give a construction for an induced-universal graph for the family of graphs on n vertices with degree at most r, which has \(Cn^{\lfloor (r+1)/2\rfloor}\) vertices and \(Dn^{2\lfloor (r+1)/2\rfloor -1}\) edges, where C and D are constants depending only on r. This construction is nearly optimal when r is even in that such an induced-universal graph must have at least cn ^r/2 vertices for some c depending only on r.Our construction is explicit in that no probabilistic tools are needed to show that the graph exists or that a given graph is induced-universal. The construction also extends to multigraphs and directed graphs with bounded degree.     

Distance-Balanced Graphs

Distance-balanced graphs are introduced as graphs in which every edge uv has the following property The number of vertices closer to u than to v is equal to the number of vertices closer to v than to u. Basic properties of these graphs are obtained. The new concept is connected with symmetry conditions in graphs and local operations on graphs are studied with respect to it. Distance-balanced Cartesian and lexicographic products of graphs are also characterized. Several open problems are posed along the way. Received August 31, 2005     

F-Continuous Graphs

For a nontrivial connected graph F, the F-degree of a vertex in a graph G is the number of copies of F in G containing . A graph G is F-continuous (or F-degree continuous) if the F-degrees of every two adjacent vertices of G differ by at most 1. All P₃-continuous graphs are determined. It is observed that if G is a nontrivial connected graph that is F-continuous for all nontrivial connected graphs F, then either G is regular or G is a path. In the case of a 2-connected graph F, however, there always exists a regular graph that is not F-continuous. It is also shown that for every graph H and every 2-connected graph F, there exists an F-continuous graph G containing H as an induced subgraph.     

Degree-Continuous Graphs

A graph G is degree-continuous if the degrees of every two adjacent vertices of G differ by at most 1. A finite nonempty set S of integers is convex if k S for every integer k with min(S)kmax(S). It is shown that for all integers r > 0 and s 0 and a convex set S with min(S) = r and max(S) = r+s, there exists a connected degree-continuous graph G with the degree set S and diameter 2s+2. The minimum order of a degree-continuous graph with a prescribed degree set is studied. Furthermore, it is shown that for every graph G and convex set S of positive integers containing the integer 2, there exists a connected degree-continuous graph H with the degree set S and containing G as an induced subgraph if and only if max(S)(G) and G contains no r-regular component where r = max(S).     

Biclique-Helly Graphs

A graph is biclique-Helly when its family of (maximal) bicliques is a Helly family. We describe characterizations for biclique-Helly graphs, leading to polynomial time recognition algorithms. In addition, we relate biclique-Helly graphs to the classes of clique-Helly, disk-Helly and neighborhood-Helly graphs.     

Minimum Size of n-Factor-Critical Graphs and k-Extendable Graphs

We determine the minimum size of n-factor-critical graphs and that of k-extendable bipartite graphs, by considering Harary graphs and related graphs. Moreover, we determine the minimum size of k-extendable non-bipartite graphs for k = 1, 2, and pose a related conjecture for general k.