共查询到20条相似文献,搜索用时 546 毫秒
1.
Suohai Fan 《Southeast Asian Bulletin of Mathematics》2001,25(2):217-221
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.
Guiyun Chen 《中国科学A辑(英文版)》1997,40(8):807-812
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.
The Entire Coloring of Series-Parallel Graphs 总被引:2,自引:0,他引:2
Jian-liangWu Yu-liangWu 《应用数学学报(英文版)》2005,21(1):61-66
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. 相似文献
6.
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. 相似文献
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
XU Junming 《数学年刊B辑(英文版)》2000,21(1):39-42
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 Linear Time Algorithm for the Minimum-weight Feedback Vertex Set Problem in Series-parallel Graphs
Shao-qiangZhang Guo-junLi Shu-guangLi 《应用数学学报(英文版)》2004,20(4):579-588
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 orG≅Q
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.
YanLiu 《应用数学学报(英文版)》2004,20(4):641-646
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.
Jie-hua MAI~ Tai-xiang SUN~ 《中国科学A辑(英文版)》2007,50(12):1818-1824
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.
MENGJIXIANG 《高校应用数学学报(英文版)》1996,11(4):497-500
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.
Xiangfei Ni 《Semigroup Forum》2009,78(1):34-53
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). 相似文献