首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 15 毫秒
1.
There are different endomorphisms for a graph. For a more systematic treatment of these endomorphisms the endomorphism spectrum and the endomorphism type of a graph are defined. Knauer characterized trees using their endomorphism types. The endomorphism type of bipartite graphs with diameter three and girth six is given in this paper.AMS Subject Classification (1991): 05C25 20M20Supported by the National Natural Science Foundation of China (19901012)  相似文献   

2.
It is proved that a Suzuki-Ree group can he characterized by the bet of its order components Project partially supported by the National Natural Science Foundation of China and Ph. D. Foundation of Southwest China Normal University.  相似文献   

3.
This paper determines all commutative zero divisor semigroups whose zero divisor graph is a complete graph (finite or infinite), or a complete graph (finite or infinite) with one additional end vertex, and gives formulas for the numbers of all such semigroups with n elements. The research of T. Wu is supported by the National Natural Science Foundation of China (Grant No. 10671122) and the Natural Science Foundation of Shanghai (Grant No. 06ZR14049).  相似文献   

4.
Let G be the circuit graph of any connected matroid. We prove that G is edge-pancyclic if it has at least three vertices. This work is supported by the National Natural Science Foundation(60673047) and the Doctoral Program Foundation of Education Ministry (20040422004) of China.  相似文献   

5.
A connected graph G is said to be factor-critical if G − ν has a perfect matching for every vertex ν of G. In this paper, the factor-critical graphs G with |V(G)| maximum matchings and with |V(G)| + 1 ones are characterized, respectively. From this, some special bicritical graphs are characterized. This work is supported by the Ph.D. Programs Foundation of Ministry of Education of China (No.20070574006) and the NNSF(10201019) of China.  相似文献   

6.
The Entire Coloring of Series-Parallel Graphs   总被引:2,自引:0,他引:2  
The entire chromatic number X_(vef)(G) of a plane graph G is the minimal number of colors needed for coloring vertices, edges and faces of G such that no two adjacent or incident elements are of the same color. Let G be a series-parallel plane graph, that is, a plane graph which contains no subgraphs homeomorphic to K_(4-) It is proved in this paper that X_(vef)(G)≤max{8, △(G) 2} and X_(vef)(G)=△ 1 if G is 2-connected and △(G)≥6.  相似文献   

7.
The decomposition of the complete graph Kv into Kr×Kc's, the products of Kr and Kc,is originated from the use of DNA library screening. In this paper, we consider the case where r=2 and c = 5, and show that such a decomposition exists if and only if v ≡ 1 (mod 25).  相似文献   

8.
A graph is one-regular if its automorphism group acts regularly on the set of its arcs.Let n be a square-free integer.In this paper,we show that a cubic one-regular graph of order 2n exists if and only if n=3~tp1p2…p_s≥13,where t≤1,s≥1 and p_i's are distinct primes such that 3|(P_i—1). For such an integer n,there are 2~(s-1) non-isomorphic cubic one-regular graphs of order 2n,which are all Cayley graphs on the dihedral group of order 2n.As a result,no cubic one-regular graphs of order 4 times an odd square-free integer exist.  相似文献   

9.
10.
A NEW PROPERTY OF BINARY UNDIRECTED de BRUIJN GRAPHS   总被引:2,自引:0,他引:2  
1.IntroductionThen-dimensionalbinarydirecteddeBruijngraph,denotedbyB(n),hasthevertex-set{xlxz'xu:xiE{0,1}}.TherearetwoarcsfromavertexxlxZ'xutothevenicesxzxa'x.-lx.0andxZx3'x.-l-c.1.Then-dimensionalbinaryundirecteddeBruijngraph,denotedbyUB(n),isobtainedfromB(n)bydeletingtheorientationofthearcsandthenomittingmultipleedgesandloops.ItiswellknownthatUB(n)hasdiameternandconnectivitytwo.ThedeBruijngraphshavebeenwidelyusedincodingtheory[6].Theyhavebeenalsoproposedasapossiblegoodcomputeri…  相似文献   

11.
A feedback vertex set is a subset of vertices in a graph, whose deletion from the graph makes the resulting graph acyclic. In this paper, we study the minimum-weight feedback vertex set problem in seriesparallel graphs and present a linear-time exact algorithm to solve it.  相似文献   

12.
Planar graphs with maximum degree Δ ⩾ 8 and without 5- or 6-cycles with chords are proved to be (δ + 1)-totally-colorable. This work was supported by Natural Science Foundation of Ministry of Education of Zhejiang Province, China (Grant No. 20070441)  相似文献   

13.
LetG be a finite group and let S be a nonempty subset of G not containing the identity element 1. The Cayley (di) graph X = Cay(G, S) of G with respect to S is defined byV (X)=G, E (X)={(g,sg)|g∈G, s∈S} A Cayley (di) graph X = Cay (G,S) is said to be normal ifR(G) ◃A = Aut (X). A group G is said to have a normal Cayley (di) graph if G has a subset S such that the Cayley (di) graph X = Cay (G, S) is normal. It is proved that every finite group G has a normal Cayley graph unlessG≅ℤ4×ℤ2 orGQ 8×ℤ 2 r (r⩾0) and that every finite group has a normal Cayley digraph, where Zm is the cyclic group of orderm and Q8 is the quaternion group of order 8. Project supported by the National Natural Science Foundation of China (Grant No. 10231060) and the Doctorial Program Foundation of Institutions of Higher Education of China.  相似文献   

14.
The maximum matching graph of a graph has a vertex for each maximum matching and an edge for each pair of maximum matchings which differ by exactly one edge. In this paper, we obtain a lower bound of distance between two vertices of maximum matching graph, and give a necessary and sufficient condition that the bound can be reached.  相似文献   

15.
Let G be a graph and f:G→G be continuous.Denote by R(f) andΩ(f) the set of recurrent points and the set of non-wandering points of f respectively.LetΩ_0(f) = G andΩ_n(f)=Ω(f|_(Ω_(n-1)(f))) for all n∈N.The minimal m∈NU {∞} such thatΩ_m(f)=Ω_(m 1)(f) is called the depth of f.In this paper,we show thatΩ_2 (f)=(?) and the depth of f is at most 2.Furthermore,we obtain some properties of non-wandering points of f.  相似文献   

16.
The total chromatic number of series-parallel graphs of maximum degree greater than or equal to 4 will be determined using the double inductions and the method of exchanging colors from the aspect of configuration property. Thus, the result of paper [7] is a special case of this paper. This research was supported by National Natural Science Foundation of China under grant NSFC60503002  相似文献   

17.
1.IntroductionLetG=(V,E,W)beaconnected,weightedandundirectedgraph,VeEE,w(e)(相似文献   

18.
We prove that the connectivities of minimal Cayley coset digraphs are their regular degrees.  相似文献   

19.
Almost all Cayley graphs are hamiltonian   总被引:3,自引:0,他引:3  
It has been conjectured that there is a hamiltonian cycle in every finite connected Cayley graph. In spite of the difficulty in proving this conjecture, we show that almost all Cayley graphs are hamiltonian. That is, as the order n of a groupG approaches infinity, the ratio of the number of hamiltonian Cayley graphs ofG to the total number of Cayley graphs ofG approaches 1.Supported by the National Natural Science Foundation of China, Xinjiang Educational Committee and Xinjiang University.  相似文献   

20.
The concept of quasi-adequate transversals is introduced. Some properties and characterizations for abundant semigroups with a multiplicative quasi-adequate transversal are obtained. In particular, a structure theorem for such abundant semigroups is given. Finally, some special cases are considered. This research was partially supported by the National Natural Science Foundation of China (No. 10571077) and the Natural Science Foundation of Gansu Province (No. 3ZS052-A25-017).  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号