共查询到20条相似文献,搜索用时 15 毫秒
1.
Xingui Fang 《Journal of Combinatorial Theory, Series A》2011,118(3):1039-1051
In this paper we investigate locally primitive Cayley graphs of finite nonabelian simple groups. First, we prove that, for any valency d for which the Weiss conjecture holds (for example, d?20 or d is a prime number by Conder, Li and Praeger (2000) [1]), there exists a finite list of groups such that if G is a finite nonabelian simple group not in this list, then every locally primitive Cayley graph of valency d on G is normal. Next we construct an infinite family of p-valent non-normal locally primitive Cayley graph of the alternating group for all prime p?5. Finally, we consider locally primitive Cayley graphs of finite simple groups with valency 5 and determine all possible candidates of finite nonabelian simple groups G such that the Cayley graph Cay(G,S) might be non-normal. 相似文献
2.
Bálint Birszki 《代数通讯》2013,41(1):23-28
A permutation group G ≤ Sym(X) on a finite set X is sharp if |G|=∏ l?L(G)(|X| ? l), where L(G) = {|fix(g)| | 1 ≠ g ? G}. We show that no finite primitive permutation groups of twisted wreath type are sharp. 相似文献
3.
Robert W. Baddeley 《Journal of Algebraic Combinatorics》1993,2(3):215-237
The paper addresses a part of the problem of classifying all 2-arc transitive graphs: namely, that of finding all groups acting 2-arc transitively on finite connected graphs such that there exists a minimal normal subgroup that is nonabelian and regular on vertices. A construction is given for such groups, together with the associated graphs, in terms of the following ingredients: a nonabelian simple group T, a permutation group P acting 2-transitively on a set , and a map F : Tsuch that x = x
–1 for all x
F() and such that Tis generated by F(). Conversely we show that all such groups and graphs arise in this way. Necessary and sufficient conditions are found for the construction to yield groups that are permutation equivalent in their action on the vertices of the associated graphs (which are consequently isomorphic). The different types of groups arising are discussed and various examples given. 相似文献
4.
Masato Tomiyama 《Discrete Mathematics》2001,240(1-3):281-294
Let Γ denote a distance-regular graph with diameter d3. Let E, F denote nontrivial primitive idempotents of Γ such that F corresponds to the second largest or the least eigenvalue. We investigate the situation that there exists a primitive idempotent H of Γ such that EF is a linear combination of F and H. Our main purpose is to obtain the inequalities involving the cosines of E, and to show that equality is closely related to Γ being Q-polynomial with respect to E. This generalizes a result of Lang on bipartite graphs and a result of Pascasio on tight graphs. 相似文献
5.
6.
7.
The Randić index R(G) of a graph G is defined by , where d(u) is the degree of a vertex u in G and the summation extends over all edges uv of G. A conjecture about the Randić index says that for any triangle-free graph G of order n with minimum degree δ≥k≥1, one has , where the equality holds if and only if G=Kk,n−k. In this short note we give a confirmative proof for the conjecture. 相似文献
8.
Let K
m,n
be a complete bipartite graph with two partite sets having m and n vertices, respectively. A P
v
-factorization of K
m,n
is a set of edge-disjoint P
v
-factors of K
m,n
which partition the set of edges of K
m,n
. When v is an even number, Wang and Ushio gave a necessary and sufficient condition for existence of P
v
-factorization of K
m,n
. When k is an odd number, Ushio in 1993 proposed a conjecture. Very recently, we have proved that Ushio’s conjecture is true when
v = 4k − 1. In this paper we shall show that Ushio Conjecture is true when v = 4k − 1, and then Ushio’s conjecture is true. That is, we will prove that a necessary and sufficient condition for the existence
of a P
4k+1-factorization of K
m,n
is (i) 2km≤(2k+1)n, (ii) 2kn≤(2k+1)m, (iii) m+n≡0 (mod 4k+1), (iv) (4k+1)mn/[4k(m+n)] is an integer. 相似文献
9.
A congruence on a conjecture of van Hamme is established. This result confirms a particular case of a congruence conjecture of Swisher. 相似文献
10.
Roland Kaschek 《Discrete Mathematics》2010,310(8):1275-1281
This paper proves a necessary and sufficient condition for the endomorphism monoid of a lexicographic product G[H] of graphs G,H to be the wreath product of the monoids and . The paper also gives respective necessary and sufficient conditions for specialized cases such as for unretractive or triangle-free graphs G. 相似文献
11.
Norbert Polat 《Journal of Graph Theory》2003,43(4):280-298
A (finite or infinite) graph G is constructible if there exists a well‐ordering ≤ of its vertices such that for every vertex x which is not the smallest element, there is a vertex y < x which is adjacent to x and to every neighbor z of x with z < x. Particular constructible graphs are Helly graphs and connected bridged graphs. In this paper we study a new class of constructible graphs, the class of locally Helly graphs. A graph G is locally Helly if, for every pair (x,y) of vertices of G whose distance is d ≥ 2, there exists a vertex whose distance to x is d ? 1 and which is adjacent to y and to all neighbors of y whose distance to x is at most d. Helly graphs are locally Helly, and the converse holds for finite graphs. Among different properties we prove that a locally Helly graph is strongly dismantable, hence cop‐win, if and only if it contains no isometric rays. We show that a locally Helly graph G is finitely Helly, that is, every finite family of pairwise non‐disjoint balls of G has a non‐empty intersection. We give a sufficient condition by forbidden subgraphs so that the three concepts of Helly graphs, of locally Helly graphs and of finitely Helly graphs are equivalent. Finally, generalizing different results, in particular those of Bandelt and Chepoi 1 about Helly graphs and bridged graphs, we prove that the Helly number h(G) of the geodesic convexity in a constructible graph G is equal to its clique number ω(G), provided that ω(G) is finite. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 280–298, 2003 相似文献
12.
P. Ille 《Discrete Mathematics》2009,309(11):3518-3522
In 1960, Sabidussi conjectured that if a graph G is isomorphic to the lexicographic product G[G], then the wreath product of by itself is a proper subgroup of . A positive answer is provided by constructing an automorphism Ψ of G[G] which satisfies: for every vertex x of G, there is an infinite subset I(x) of V(G) such that Ψ({x}×V(G))=I(x)×V(G). 相似文献
13.
Stefan Hougardy 《Discrete Mathematics》2006,306(22):2962-2963
Hoàng and Tu [On the perfect orderability of unions of two graphs, J. Graph Theory 33 (2000) 32-43] conjectured that a weakly triangulated graph which does not contain a chordless path with six vertices is perfectly orderable. We present a counter example to this conjecture. 相似文献
14.
The authors investigate locally primitive bipartite regular
connected graphs of order $18p$. It is shown that such a graph
is either arc-transitive or isomorphic to one of the Gray graph and the Tutte $12$-cage. 相似文献
15.
16.
In this paper we give a classification of a family of symmetric graphs with complete 2-arc-transitive quotients. Of particular interest are two subfamilies of graphs which admit an arc-transitive action of a projective linear group. The graphs in these subfamilies can be defined in terms of the cross ratio of certain 4-tuples of elements of a finite projective line, and thus may be called the second type ‘cross ratio graphs’, which are different from the ‘cross ratio graphs’ studied in [A. Gardiner, C. E. Praeger, S. Zhou, Cross-ratio graphs, J. London Math. Soc. (2) 64 (2001), 257–272]. We also give a combinatorial characterisation of such second type cross ratio graphs. 相似文献
17.
Byeong Moon Kim Byung Chul Song Woonjae Hwang 《Linear algebra and its applications》2007,420(2-3):648-662
A graph G = (V, E) on n vertices is primitive if there is a positive integer k such that for each pair of vertices u, v of G, there is a walk of length k from u to v. The minimum value of such an integer, k, is the exponent, exp(G), of G. In this paper, we find the minimum number, h(n, k), of edges of a simple graph G on n vertices with exponent k, and we characterize all graphs which have h(n, k) edges when k is 3 or even. 相似文献
18.
On a conjecture of the Euler numbers 总被引:1,自引:0,他引:1
The main purpose of this paper is to prove a conjecture of the Euler numbers and its generalization by using the analytic methods. That is, for any prime and integer α?1 we proved , where E2n are the Euler numbers and ?(n) the Euler function. 相似文献
19.
A graph Г is said to be G-locally primitive, where G is a subgroup of automorphisms of Г, if the stabiliser Ga of a vertex α acts primitively on the set Г( α ) of vertices of Г adjacent to α. For a finite non-abelian simple group L
and a Cayley subset S of L, suppose that L ⊴ G ⩽ Aut( L), and the Cayley graph Г = Cay ( L, S) is G-locally primitive. In
this paper we prove that L is a simple group of Lie type, and either the valency of Г is an add prine divisor of |Out(L)|, orL =PΩ
8
+
(q) and Г has valency 4. In either cases, it is proved that the full automorphism group of Г is also almost simple with the
same socle L. 相似文献
20.
Xiao Song Lin 《数学学报(英文版)》2001,17(3):361-380
We present a twisted version of the Alexander polynomial associated with a matrix representation of the knot group. Examples
of two knots with the same Alexander module but different twisted Alexander polynomials are given. 相似文献