图的割宽极值问题

The problem studied in this paper is to determine e(p, C), the minimum size of a connected graph G with given vertex number p and cut-width C.     

Moore Graphs and Cycles Are Extremal Graphs for Convex Cycles

Let denote the number of convex cycles of a simple graph G of order n, size m, and girth . It is proved that and that equality holds if and only if G is an even cycle or a Moore graph. The equality also holds for a possible Moore graph of diameter 2 and degree 57 thus giving a new characterization of Moore graphs.     

On the Structure of Graphs with Given Odd Girth and Large Minimum Degree

We study minimum degree conditions for which a graph with given odd girth has a simple structure. For example, the classical work of Andrásfai, Erd?s, and Sós implies that every n‐vertex graph with odd girth and minimum degree bigger than must be bipartite. We consider graphs with a weaker condition on the minimum degree. Generalizing results of Häggkvist and of Häggkvist and Jin for the cases and 3, we show that every n‐vertex graph with odd girth and minimum degree bigger than is homomorphic to the cycle of length . This is best possible in the sense that there are graphs with minimum degree and odd girth that are not homomorphic to the cycle of length . Similar results were obtained by Brandt and Ribe‐Baumann.     

一类本原无向图的广义上指数的极图

设R（n,d)表示由全体恰含d个环点的n(n≥3）阶本原无向图所构成的集合,F(n,d,k)为R(n,d)中图的第k重上广义本原指数的量大值,1≤d≤n,2≤k≤n-1。本文给出了第k重上广义本原指数达到F(n,d,k)的极图的完全刻画。     

Extremal Problems for Imbalanced Edges

Albertson [2] has introduced the imbalance of an edge e=uv in a graph G as |d_G(u)−d_G(v)|. If for a graph G of order n and size m the minimum imbalance of an edge of G equals d, then our main result states that with equality if and only if G is isomorphic to We also prove best-possible upper bounds on the number of edges uv of a graph G such that |d_G(u)−d_G(v)|≥d for some given d.     

An Extremal Property of Turán Graphs,II

Let denote Turán's graph—the complete 2‐partite graph on n vertices with partition sizes as equal as possible. We show that for all , the graph has more proper vertex colorings in at most 4 colors than any other graph with the same number of vertices and edges.     

An Extremal Characterization of the Incidence Graphs of Projective Planes

Let G be a 4-cycle free, bipartite graph on 2n vertices with partitions of equal cardinality n. Let c₆(G) denote the number of cycles of length 6 in G. We prove that for n 3, c₆(G) , where , with equality if and only if G is the incidence point-line graph of a projective plane.     

Extremal subgraphs of random graphs

We prove that there is a constant c > 0, such that whenever p ≥ n^‐c, with probability tending to 1 when n goes to infinity, every maximum triangle‐free subgraph of the random graph G_n,p is bipartite. This answers a question of Babai, Simonovits and Spencer (Babai et al., J Graph Theory 14 (1990) 599–622). The proof is based on a tool of independent interest: we show, for instance, that the maximum cut of almost all graphs with M edges, where M ? n and M ≤ /2, is “nearly unique”. More precisely, given a maximum cut C of G_n,M, we can obtain all maximum cuts by moving at most \begin{align*}\mathcal{O}(\sqrt{n^3/M})\end{align*} vertices between the parts of C. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

Smallest Vertex‐Transitive Graphs of Given Degree and Diameter

For every d and k, we determine the smallest order of a vertex‐transitive graph of degree d and diameter k, and in each such case we show that this order is achieved by a Cayley graph.     

Extremal graphs having no matching cuts

A graph G = (V, E) is matching immune if there is no matching cut in G. We show that for any matching immune graph G, |E|≥?3(|V|?1)/2?. This bound is tight, as we define operations that construct, from a given vertex, exactly the class of matching immune graphs that attain the bound. © 2011 Wiley Periodicals, Inc. J Graph Theory 69:206‐222, 2012 .     

Decompositions of Graphs into Fans and Single Edges

Given two graphs G and H , an H‐decomposition of G is a partition of the edge set of G such that each part is either a single edge or forms a graph isomorphic to H . Let be the smallest number ? such that any graph G of order n admits an H‐decomposition with at most ? parts. Pikhurko and Sousa conjectured that for and all sufficiently large n , where denotes the maximum number of edges in a graph on n vertices not containing H as a subgraph. Their conjecture has been verified by Özkahya and Person for all edge‐critical graphs H . In this article, the conjecture is verified for the k‐fan graph. The k‐fan graph , denoted by , is the graph on vertices consisting of k triangles that intersect in exactly one common vertex called the center of the k‐fan.     

Mapping Planar Graphs into Projective Cubes

Projective cubes are obtained by identifying antipodal vertices of hypercubes. We introduce a general problem of mapping planar graphs into projective cubes. This question, surprisingly, captures several well‐known theorems and conjectures in the theory of planar graphs. As a special case , we prove that the Clebsch graph, a triangle‐free graph on 16 vertices, is the smallest triangle‐free graph to which every triangle‐free planar graph admits a homomorphism.     

Homomorphisms of Edge-Colored Graphs and Coxeter Groups

Let be two edge-colored graphs (without multiple edges or loops). A homomorphism is a mapping : for which, for every pair of adjacent vertices u and v of G ₁, (u) and (v) are adjacent in G ₂ and the color of the edge (u)(v) is the same as that of the edge uv.We prove a number of results asserting the existence of a graphG , edge-colored from a set C, into which every member from a given class of graphs, also edge-colored from C, maps homomorphically.We apply one of these results to prove that every three-dimensional hyperbolic reflection group, having rotations of orders from the setM ={m₁, m₂,..., m_k}, has a torsion-free subgroup of index not exceeding some bound, which depends only on the setM .     

An Extremal Problem with Excluded Subposet in the Boolean Lattice

Let 2[n] be the poset of all subsets of {1,...,n} ordered by inclusion. A poset P is said to be contained in a subposet F of 2[n] as a subposet if there exists a subposet P' of F that is isomorphic to P. In this paper we will give an estimate on the size of a maximally sized subposet of 2[n] under the assumption that the subposet does not contain Y(u,v) = ({a1,...,au, b1,...,bv}, {a1< ··· < au, au< b1, au< b2,...,au< bv}) as a subposet.     

Bipartite Subgraphs of Graphs with Maximum Degree Three

We prove that for a connected graph G with maximum degree 3 there exists a bipartite subgraph of G containing almost of the edges of G. Furthermore, we completely characterize the set of all extremal graphs, i.e. all connected graphs G=(V, E) with maximum degree 3 for which no bipartite subgraph has more than of the edges; |E| denotes the cardinality of E. For 2-edge-connected graphs there are two kinds of extremal graphs which realize the lower bound . Received: July 17, 1995 / Revised: April 5, 1996     

Induced Decompositions of Graphs

We consider those graphs G that admit decompositions into copies of a fixed graph F, each copy being an induced subgraph of G. We are interested in finding the extremal graphs with this property, that is, those graphs G on n vertices with the maximum possible number of edges. We discuss the cases where F is a complete equipartite graph, a cycle, a star, or a graph on at most four vertices.