Strong edge-coloring for planar graphs with large girth

A strong edge-coloring of a graph $G=(V,E)$ is a partition of its edge set $E$ into induced matchings. Let $G$ be a connected planar graph with girth $k\ge 26$ and maximum degree $\Delta$. We show that either $G$ is isomorphic to a subgraph of a very special $\Delta$-regular graph with girth $k$, or $G$ has a strong edge-coloring using at most $2\Delta +\lceil \frac{12(\Delta -2)}{k}\rceil$ colors.     

Directed triangles in directed graphs

We show that each directed graph (with no parallel arcs) on n vertices, each with indegree and outdegree at least n/twhere t=2.888997… contains a directed circuit of length at most 3.     

Sparse <Emphasis Type="Italic">H</Emphasis>-Colourable Graphs of Bounded Maximum Degree

Let F be a graph of order at most k. We prove that for any integer g there is a graph G of girth at least g and of maximum degree at most 5k¹³ such that G admits a surjective homomorphism c to F, and moreover, for any F-pointed graph H with at most k vertices, and for any homomorphism h from G to H there is a unique homomorphism f from F to H such that h=fc. As a consequence, we prove that if H is a projective graph of order k, then for any finite family of prescribed mappings from a set X to V(H) (with ||=t), there is a graph G of arbitrary large girth and of maximum degree at most 5k^26mt (where m=|X|) such that and up to an automorphism of H, there are exactly t homomorphisms from G to H, each of which is an extension of an f.Supported in part by the National Science Council under grant NSC89-2115-M-110-012Final version received: June 9, 2003     

On the girth of extremal graphs without shortest cycles

Let EX(ν;{C₃,…,C_n}) denote the set of graphs G of order ν that contain no cycles of length less than or equal to n which have maximum number of edges. In this paper we consider a problem posed by several authors: does G contain an n+1 cycle? We prove that the diameter of G is at most n−1, and present several results concerning the above question: the girth of G is g=n+1 if (i) ν≥n+5, diameter equal to n−1 and minimum degree at least 3; (ii) ν≥12, ν∉{15,80,170} and n=6. Moreover, if ν=15 we find an extremal graph of girth 8 obtained from a 3-regular complete bipartite graph subdividing its edges. (iii) We prove that if ν≥2n−3 and n≥7 the girth is at most 2n−5. We also show that the answer to the question is negative for ν≤n+1+⌊(n−2)/2⌋.     

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.     

Up-Embeddability of a Graph by Order and Girth

Let G be a connected graph of order n and girth g. If d_G(u) + d_G(v) ≥ n − 2g + 5 for any two non-adjacent vertices u and v, then G is up-embeddable. Further more, the lower bound is best possible. Similarly the result of k-edge connected simple graph with girth g is also obtained, k = 2,3. Partially supported by the Postdoctoral Seience Foundation of Central South University and NNSFC under Grant No. 10751013.     

几类特殊测地块的构造(英)

本文给出了一种构造给定直径d和围长g的测地块的方法．它是文［1］中构造法的推广，解决了文［1］中待研究的几个问题．同时，对文［1］中的一个错误进行了修正．