Graphs of Large Girth with Prescribed Partial Circular Colourings

This paper completes the constructive proof of the following result: Suppose p/q2 is a rational number, A is a finite set and f₁,f₂,···,f_n are mappings from A to {0,1,···,p–1}. Then for any integer g, there is a graph G=(V,E) of girth at least g with such that G has exactly n (p,q)-colourings (up to equivalence) g₁,g₂,···,g_n, and each g_i is an extension of f_i. A probabilistic proof of this result was given in [8]. A constructive proof of the case p/q3 was given in [7].This research was partially supported by the National Science Council under grant NSC91-2115-M-110-004     

n-Tuple Coloring of Planar Graphs with Large Odd Girth

 The main result of the papzer is that any planar graph with odd girth at least 10k−7 has a homomorphism to the Kneser graph G _k ^{2 k +1}, i.e. each vertex can be colored with k colors from the set {1,2,…,2k+1} so that adjacent vertices have no colors in common. Thus, for example, if the odd girth of a planar graph is at least 13, then the graph has a homomorphism to G ₂ ⁵, also known as the Petersen graph. Other similar results for planar graphs are also obtained with better bounds and additional restrictions. Received: June 14, 1999 Final version received: July 5, 2000     

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.     

Edge Maximal Non-Bipartite Graphs Without Odd Cycles of Prescribed Lengths

 Let ?(n;3,5,…,2k+1) denote the class of non-bipartite graphs on n vertices having no odd cycle of length ≤2k+1. We prove that for every G∈?(n;3,5,…,2k+1) and characterize the extremal graphs. We also study the subclass ℋ(n;3,5,…,2k+1) consisting of the hamiltonian members of ?(n;3,5,…, 2k+1). For this subclass the above upper bound holds for odd n. For even n we establish the following sharp upper bound:

Extremal Systems with Upper-Bounded Odd Intersections

In this paper we determine the maximum cardinality m of a family A= {A ₁,..., A _m} of subsets of a set of n elements with the property that for each A _i there are at most s A _j such that |A _i ∩ A _j | is odd (even). A tight upper bound is given in the case s < c(2 ^n,2/n). In the remaining cases we give an asymptotically tight upper bound. As an application we give a tight upper-bound for the cardinality of a family with even multi-intersection. Both results generalize a result of Berlekamp and Graver.     

Ramanujan Graphs with Small Girth

We construct an innite family of (q + 1)-regular Ramanujan graphs X _n of girth 1. We also give covering maps X _n+1 X _n such that the minimal common covering of all the X _n s is the universal covering tree.     

Biregular Cages of Odd Girth

Biregular ‐cages are graphs of girth g that contain vertices of degrees r and m and are of the smallest order among all such graphs. We show that for every and every odd , there exists an integer m₀ such that for every even , the biregular ‐cage is of order equal to a natural lower bound analogous to the well‐known Moore bound. In addition, when r is odd, the restriction on the parity of m can be removed, and there exists an integer m₀ such that a biregular ‐cage of order equal to this lower bound exists for all . This is in stark contrast to the result classifying all cages of degree k and girth g whose order is equal to the Moore bound.     

Total Domination in Graphs with Given Girth

A set S of vertices in a graph G without isolated vertices is a total dominating set of G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number γ _t (G) of G. In this paper, we establish an upper bound on the total domination number of a graph with minimum degree at least two in terms of its order and girth. We prove that if G is a graph of order n with minimum degree at least two and girth g, then γ _t (G) ≤ n/2 + n/g, and this bound is sharp. Our proof is an interplay between graph theory and transversals in hypergraphs. Michael A. Henning: Research supported in part by the South African National Research Foundation and the University of KwaZulu-Natal.     

Hypohamiltonian Planar Cubic Graphs with Girth 5

A graph is called hypohamiltonian if it is not hamiltonian but becomes hamiltonian if any vertex is removed. Many hypohamiltonian planar cubic graphs have been found, starting with constructions of Thomassen in 1981. However, all the examples found until now had 4‐cycles. In this note we present the first examples of hypohamiltonian planar cubic graphs with cyclic connectivity 5, and thus girth 5. We show by computer search that the smallest members of this class are three graphs with 76 vertices.     

Regular and Maximal Graphs with Prescribed Tripartite Graph as a Star Complement*

Let G be a graph of order n and μ be an adjacency eigenvalue of G with multiplicity k ≥ 1. A star complement H for μ in G is an induced subgraph of G of order n-k with no eigenvalue μ, and the subset X = V(G-H) is called a star set for μ in G. The star complement provides a strong link between graph structure and linear algebra. In this paper, the authors characterize the regular graphs with K_2,2,s(s ≥ 2) as a star complement for all possible eigenvalues, the maximal graphs with K     

关于奇算术图

本文讨论了$n$个$m$长圈有一个公共结点图$C^n_m$, $n$个$m$长圈与$t$长路有一个公共结点图$C^n_m\cdot P_t$, $n$个$m$阶完全图有一个公共结点图$K^n_m$和星形图的同胚图的奇算术性问题.给出了完全图,完全二部图和圈是奇算术的充要条件.     

Acyclic Colourings of Planar Graphs with Large Girth

A proper vertex-colouring of a graph is acyclic if there areno 2-coloured cycles. It is known that every planar graph isacyclically 5-colourable, and that there are planar graphs withacyclic chromatic number _a = 5 and girth g = 4. It is provedhere that a planar graph satisfies _a 4 if g 5 and _a 3 ifg 7.     

Edge Coloring of Embedded Graphs with Large Girth

Let G be a simple graph embedded in the surface of Euler characteristic ()0. Denote _e(G), and g the edge chromatic number, the maximum degree and the girth of the graph G, respectively. The paper shows that _e(G)= if 5 and g4, or 4 and g5, or 3 and g9. In addition, if ()>0, then _e(G)= if 3 and g8. Acknowledgments.The authors would like to thank Dr. C.Q. Zhang for carefully reading several versions of this paper during its preparation and for suggesting several stylistic changes that have improved the overall presentation.     

有约束条件的图的分数k-因子

设G是一个简单的无向图，若G不是完全图，G的孤立韧度定义为I(G)=min{｜s｜／i(G-S)：S∈V(G)，i(G-S)≥2)；否则令I(G)=∞．对与图的孤立韧度I(G)密切相关的新参数，I’(G)，若G不是完全图，定义I’(G)=min{｜s｜/i(G-S)-1:S∈V(G)，i(G-S)≥2}；否则I’(G)=∞本文研究了新参数I‘(G)与图的分数κ-因子的关系，给出了具有某些约束条件的图的分数κ-因子存在的一些充分条件．     

Conformal Killing Graphs with Prescribed Mean Curvature

We prove the existence and uniqueness of graphs with prescribed mean curvature function in a large class of Riemannian manifolds which comprises spaces endowed with a conformal Killing vector field.     

Locally Symmetric Graphs of Girth 4

We classify the family of connected, locally symmetric graphs of girth 4 (finite and infinite). They are all regular, with the exception of the complete bipartite graph . There are, up to isomorphism, exactly four such k‐regular graphs for every , one for , two for , and exactly three for every infinite cardinal k. In the last paragraph, we consider locally symmetric graphs of girth >4.