具有完全正则自同态半群的分裂图

本文给出了具有完全正则自同态半群的分裂图的结构特征．其证明方法有望应用于其他图族自同态半群的正则性及完全正则性的研究．     

二部图的E-H-不可收缩性

By End（G） and hEnd（G） we denote the set of endomorphisms and half-strong endomorphisms of a graph G respectively. A graph G is said to be E-H-unretractive if End（G） = hEnd（G）. A general characterization of an E-H-unretractive graph seems to be difficult. In this paper, bipartite graphs with E-H-unretractivity are characterized explicitly.     

Endomorphism Classes of Ordered Sets,Graphs and Lattices

Order - Given a structure S, what other structures S' on the same underlying set satisfy End S $ \subseteq$ End S'? We answer this question for the cases of ordered sets, reflexive...     

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     

图的字典序积和自同态幺半群

Ｆ．Ｈａｒａｒｙ￣［１］和Ｇ．Ｓａｂｉｄｕｓｓｉ￣［２］考虑过图Ｘ和ｙ的字典序积Ｘ［Ｙ］的自同构群ＡｕｔＸ［Ｙ］与它们各自的自同构群的圈积ＡｕｔＸ［ＡｕｔＹ］的关系，并给出了两者相等的一种刻划．在本文，我们考虑更广意义上的问题，即Ｘ［Ｙ］的自同态幺半群ＥｎｄＸ［Ｙ］与各自的自同态幺半群的圈积ＥｎｄＸ［ＥｎｄＹ］的关系，也给出了两者相等的一种刻划，同时得到了下面结果：如果Ｘ和Ｙ都是不含Ｋ＿３导出子图的连通图，且其中之一图有奇数围长，那么ＥｎｄＸ［Ｙ］＝ＥｎｄＸ［ＥｎｄＹ］．     

A Characterization of Distance-Regular Graphs with Diameter Three

We characterize the distance-regular graphs with diameter three by giving an expression for the number of vertices at distance two from each given vertex, in terms of the spectrum of the graph.     

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.     

The Spectra of Coxeter Graphs

We determine the spectra of the finite Coxeter graphs defined by a terminal node of the Coxeter diagram, and the spectra of their thick equivalents.     

二部图的单特征值

一个图的特征值通常指的是它的邻接矩阵的特征值,在图的所有特征值中,重数为1的特征值即所谓的单特征值具有特殊的重要性.确定一个图的单特征值是一个比较困难的问题,主要是没有一个通用的方法.1969年,Petersdorf和Sachs给出了点传递图单特征值的取值范围,但是对于具体的点传递图还需要根据图本身的特性来确定它的单特...     

Decomposition of Complete Graphs into Isomorphic Complete Bipartite Graphs

A decomposition of a complete graph into disjoint copies of a complete bipartite graph is called a ‐design of order n. The existence problem of ‐designs has been completely solved for the graphs for , for , K_{2, 3} and K_{3, 3}. In this paper, I prove that for all , if there exists a ‐design of order N, then there exists a ‐design of order n for all (mod ) and . Giving necessary direct constructions, I provide an almost complete solution for the existence problem for complete bipartite graphs with fewer than 18 edges, leaving five orders in total unsolved.     

On Locally Projective Graphs of Girth 5

Let be a graph and G be a 2-arc transitive automorphism group of . For a vertex x let G(x)^(x) denote the permutation group induced by the stabilizer G(x) of x in G on the set (x) of vertices adjacent to x in . Then is said to be a locally projective graph of type (n,q) if G(x)^(x) contains PSL_n(q) as a normal subgroup in its natural doubly transitive action. Suppose that is a locally projective graph of type (n,q), for some n 3, whose girth (that is, the length of a shortest cycle) is 5 and suppose that G(x) acts faithfully on (x). (The case of unfaithful action was completely settled earlier.) We show that under these conditions either n=4, q=2, has 506 vertices and , and contains the Wells graph on 32 vertices as a subgraph. In the latter case if, for a given n, at least one graph satisfying the conditions exists then there is a universal graph W(n) of which all other graphs for this n are quotients. The graph W(3) satisfies the conditions and has 2²⁰ vertices.     

围长为3的点可迁图的3限制边连通度

设G是阶至少为6的k正则连通图.如果G的围长等于3,那么它的3限制边连通度 λ3(G)≤3k-6.当G是3或者4正则连通点可迁图时等号成立,除非G是4正则图并且 λ3(G)=4.进一步,λ3(G)=4的充分必要条件是图G含有子图K4.     

Perfect Matchings of Regular Bipartite Graphs

Let G be a regular bipartite graph and . We show that there exist perfect matchings of G containing both, an odd and an even number of edges from X if and only if the signed graph , that is a graph G with exactly the edges from X being negative, is not equivalent to . In fact, we prove that for a given signed regular bipartite graph with minimum signature, it is possible to find perfect matchings that contain exactly no negative edges or an arbitrary one preselected negative edge. Moreover, if the underlying graph is cubic, there exists a perfect matching with exactly two preselected negative edges. As an application of our results we show that each signed regular bipartite graph that contains an unbalanced circuit has a 2‐cycle‐cover such that each cycle contains an odd number of negative edges.     

图的强收缩核与图的强自同态幺半群的正则性

本文研究图及其强自同态幺半群．首先刻画了图的强自同态幺半群的正则元，然后给出了此幺半群正则的充要条件．这推广了［１］和［２］中关于有限图的强自同态幺半群正则的结果．     

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.     

On Primitive Idempotents of the Strong Endomorphism Monoid of a Graph

51.IntroductionandPreIiminariesThemonoidofendomorphismsofagraph,inparticular,thatofstrongendomorphismsofagraph,hasbeentheobjectofresearchesinthetheoryofsemigroupsforquitesometime(cf.Llj-Lloj).LlJandL2jcanserveasasurvey.Theaimoftheseresearchesistocon-tributetothealgebraicanalysisofgraphs.Thesubjectyieldssomeinterestsincetheresultsoftheseresearchesmayopenvastpossibilitiesforapplicationsofsemigrouptheorytographtheo-ry.InL1]andL3j,ithasbeenprovedthatforfinitegraphG,sEnd(G),themonoidofstrongen…     

系列平行图的围长和圆可选性

本文讨论了系列平行图的圆可选性．令x_(c,l)表示圆可选性(或圆列表着色数)．本文证明了围长至少是4n 1的系列平行图的圆可选性至多为2 1/n．     

Generation of Cubic Graphs and Snarks with Large Girth

We describe two new algorithms for the generation of all non‐isomorphic cubic graphs with girth at least that are very efficient for and show how these algorithms can be restricted to generate snarks with girth at least k. Our implementation of these algorithms is more than 30, respectively 40 times faster than the previously fastest generator for cubic graphs with girth at least six and seven, respectively. Using these generators we have also generated all nonisomorphic snarks with girth at least six up to 38 vertices and show that there are no snarks with girth at least seven up to 42 vertices. We present and analyze the new list of snarks with girth 6.     

Domination in Bipartite Graphs and in Their Complements

The domatic numbers of a graph G and of its complement $\bar G$ were studied by J. E. Dunbar, T. W. Haynes and M. A. Henning. They suggested four open problems. We will solve the following ones: Characterize bipartite graphs G having $d\left( G \right) = d\left( {\bar G} \right)$ Further, we will present a partial solution to the problem: Is it true that if G is a graph satisfying $d\left( G \right) = d\left( {\bar G} \right)$ then $\gamma \left( G \right) = \gamma \left( {\bar G} \right)$ ? Finally, we prove an existence theorem concerning the total domatic number of a graph and of its complement