共查询到20条相似文献,搜索用时 187 毫秒
1.
Joel Foisy 《Journal of Graph Theory》2003,42(3):199-210
For a positive integer k, a graph G is k-ordered hamiltonian if for every ordered sequence of k vertices there is a hamiltonian cycle that encounters the vertices of the sequence in the given order. It is shown that if G is a graph of order n with 3 ≤ k ≤ n/2, and deg(u) + deg(v) ≥ n + (3k − 9)/2 for every pair u, v of nonadjacent vertices of G, then G is k-ordered hamiltonian. Minimum degree conditions are also given for k-ordered hamiltonicity. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 199–210, 2003 相似文献
2.
Let G be a finite group and π(G) be the set of all prime divisors of its order. The prime graph GK(G) of G is a simple graph with vertex set π(G), and two distinct primes p, q ∈ π(G) are adjacent by an edge if and only if G has an element of order pq. For a vertex p ∈ π(G), the degree of p is denoted by deg(p) and as usual is the number of distinct vertices joined to p. If π(G) = {p
1, p
2,...,p
k
}, where p
1 < p
2 < ... < p
k
, then the degree pattern of G is defined by D(G) = (deg(p
1), deg(p
2),...,deg(p
k
)). The group G is called k-fold OD-characterizable if there exist exactly k non-isomorphic groups H satisfying conditions |H| = |G| and D(H) = D(G). In addition, a 1-fold OD-characterizable group is simply called OD-characterizable. In the present article, we show that
the alternating group A
22 is OD-characterizable. We also show that the automorphism groups of the alternating groups A
16 and A
22, i.e., the symmetric groups S
16 and S
22 are 3-fold OD-characterizable. It is worth mentioning that the prime graph associated to all these groups are connected. 相似文献
3.
JieLU JinChengXIONG JianCHEN 《数学学报(英文版)》2004,20(3):415-422
Let G be a graph which contains exactly one simple closed curve. We prove that a continuous map f : G → G has zero topological entropy if and only if there exist at most k ≤ |(Edg(G) End(G) 3)/2] different odd numbers n1,...,nk such that Per(f) is contained in ∪i=1^k ∪j=0^∞ ni2^j, where Edg(G) is the number of edges of G and End(G) is the number of end points of G. 相似文献
4.
The signed distance-k-domination number of a graph is a certain variant of the signed domination number. If v is a vertex of a graph G, the open k-neighborhood of v, denoted by N
k
(v), is the set N
k
(v) = {u: u ≠ v and d(u, v) ⩽ k}. N
k
[v] = N
k
(v) ⋃ {v} is the closed k-neighborhood of v. A function f: V → {−1, 1} is a signed distance-k-dominating function of G, if for every vertex
. The signed distance-k-domination number, denoted by γ
k,s
(G), is the minimum weight of a signed distance-k-dominating function on G. The values of γ
2,s
(G) are found for graphs with small diameter, paths, circuits. At the end it is proved that γ
2,s
(T) is not bounded from below in general for any tree T. 相似文献
5.
Pierre Hansen Julio Kuplinsky Dominique de Werra 《Mathematical Methods of Operations Research》1997,45(1):145-160
A mixed graphG
contains both undirected edges and directed arcs. Ak-coloring ofG
is an assignment to its vertices of integers not exceedingk (also called colors) so that the endvertices of an edge have different colors and the tail of any arc has a smaller color than its head. The chromatic number (G) of a mixed graph is the smallestk such thatG
admits ak-coloring. To the best of our knowledge it is studied here for the first time. We present bounds of (G), discuss algorithms to find this quantity for trees and general graphs, and report computational experience. 相似文献
6.
Peter J. Slater 《Journal of Graph Theory》1978,2(3):209-222
For S ? V(G) the S-center and S-centroid of G are defined as the collection of vertices u ∈ V(G) that minimize es(u) = max {d(u, v): v ∈ S} and ds(u) = ∑u∈S d(u, v), respectively. This generalizes the standard definition of center and centroid from the special case of S = V(G). For 1 ? k ?|V(G)| and u ∈ V(G) let rk(u) = max {∑s∈S d(u, s): S ? V(G), |S| = k}. The k-centrum of G, denoted C(G; k), is defined to be the subset of vertices u in G for which rk(u) is a minimum. This also generalizes the standard definitions of center and centroid since C(G; 1) is the center and C(G; |V(G)|) is the centroid. In this paper the structure of these sets for trees is examined. Generalizations of theorems of Jordan and Zelinka are included. 相似文献
7.
Highly linked graphs 总被引:6,自引:0,他引:6
A graph with at least 2k vertices is said to bek-linked if, for any choices
1,...,s
k
,t
1,...,t
k
of 2k distinct vertices there are vertex disjoint pathsP
1,...,P
k
withP
i
joinings
i
tot
i
, 1ik. Recently Robertson and Seymour [16] showed that a graphG isk-linked provided its vertex connectivityk(G) exceeds
. We show here thatk(G)22k will do. 相似文献
8.
For an ordered k-decomposition
of a connected graph G and an edge e of G, the
-code of e is the k-tuple
where d(e, G
i) is the distance from e to G
i. A decomposition
is resolving if every two distinct edges of G have distinct
-codes. The minimum k for which G has a resolving k-decomposition is its decomposition dimension dim
d
(G). A resolving decomposition
of G is connected if each G
i is connected for 1 i k. The minimum k for which G has a connected resolving k-decomposition is its connected decomposition number cd(G). Thus 2 dim
d
(G) cd(G) m for every connected graph G of size m 2. All nontrivial connected graphs of size m with connected decomposition number 2 or m have been characterized. We present characterizations for connected graphs of size m with connected decomposition number m – 1 or m – 2. It is shown that each pair s, t of rational numbers with 0 < s t 1, there is a connected graph G of size m such that dim
d
(G)/m = s and cd(G)/m = t. 相似文献
9.
Letk be any field andG a finite group. Given a cohomology class α∈H
2(G,k
*), whereG acts trivially onk
*, one constructs the twisted group algebrak
αG. Unlike the group algebrakG, the twisted group algebra may be a division algebra (e.g. symbol algebras, whereG⋞Z
n×Zn). This paper has two main results: First we prove that ifD=k
α
G is a division algebra central overk (equivalentyD has a projectivek-basis) thenG is nilpotent andG’ the commutator subgroup ofG, is cyclic. Next we show that unless char(k)=0 and
, the division algebraD=k
α
G is a product of cyclic algebras. Furthermore, ifD
p is ap-primary factor ofD, thenD
p is a product of cyclic algebras where all but possibly one are symbol algebras. If char(k)=0 and
, the same result holds forD
p, p odd. Ifp=2 we show thatD
2 is a product of quaternion algebras with (possibly) a crossed product algebra (L/k,β), Gal(L/k)⋞Z
2×Z2n. 相似文献
10.
Štefan Gyürki 《Mathematica Slovaca》2009,59(2):193-200
Let k be an integer. A 2-edge connected graph G is said to be goal-minimally k-elongated (k-GME) if for every edge uv ∈ E(G) the inequality d
G−uv
(x, y) > k holds if and only if {u, v} = {x, y}. In particular, if the integer k is equal to the diameter of graph G, we get the goal-minimally k-diametric (k-GMD) graphs. In this paper we construct some infinite families of GME graphs and explore k-GME and k-GMD properties of cages.
This research was supported by the Slovak Scientific Grant Agency VEGA No. 1/0406/09. 相似文献
11.
We introduce a class of optimization problems, calleddynamic location problems, involving the processing of requests that occur sequentially at the nodes of a graphG. This leads to the definition of a new parameter of graphs, called the window indexWX(G), that measures how large a window into the future is needed to solve every instance of the dynamic location problem onG optimally on-line. We completely characterize this parameter:WX(G)k if and only ifG is a weak retract of a product of complete graphs of size at mostk. As a byproduct, we obtain two (polynomially recognizable) structural characterizations of such graphs, extending a result of Bandelt. 相似文献
12.
Let G be a finite group written multiplicatively and k a positive integer. If X is a non-empty subset of G, write X
2 = |xy | x, y X . We say that G has the small square property on k-sets if |X
2| < k
2 for any k-element subset X of G. For each group G, there is a unique m = m
G
such that G has the small square property on (m + 1)-sets but not on m-sets. In this paper we show that given any positive integer d, there is a finite group G with m
G
= d. 相似文献
13.
Xian Zu Lin 《数学学报(英文版)》2011,27(5):863-870
Let G/P be a homogenous space with G a compact connected Lie group and P a connected subgroup of G of equal rank. As the rational cohomology ring of G/P is concentrated in even dimensions, for an integer k we can define the Adams map of type k to be l
k
: H*(G/P, ℚ) → H*(G/P, ℚ), l
k
(u) = k
i
u, u ∈ H
2i
(G/P, ℚ). We show that if k is prime to the order of the Weyl group of G, then l
k
can be induced by a self map of G/P. We also obtain results which imply the condition that k is prime to the order of the Weyl group of G is necessary. 相似文献
14.
A graph G is degree-bounded-colorable (briefly, db-colorable) if it can be properly vertex-colored with colors 1,2, …, k ≤ Δ(G) such that each vertex v is assigned a color c(v) ≤ v. We first prove that if a connected graph G has a block which is neither a complete graph nor an odd cycle, then G is db-colorable. One may think of this as an improvement of Brooks' theorem in which the global bound Δ(G) on the number of colors is replaced by the local bound deg v on the color at vertex v. Extending the above result, we provide an algorithmic characterization of db-colorable graphs, as well as a nonalgorithmic characterization of db-colorable trees. We briefly examine the problem of determining the smallest integer k such that G is db-colorable with colors 1, 2,…, k. Finally, we extend these results to set coloring. © 1995, John Wiley & Sons, Inc. 相似文献
15.
Symmetric spaces or more general symmetric k-varieties can be defined as the homogeneous spaces G
k
/K
k
, where G is a reductive algebraic group defined over a field k of characteristic not 2, K the fixed point group of an involution θ of G and G
k
resp. K
k
the sets k-rational points of G resp. K. These symmetric spaces have a fine structure of root systems, characters, Weyl groups etc., similar to the underlying algebraic
group G. The relationship between the fine structure of the symmetric space and the group plays an important role in the study of
these symmetric spaces and their applications. To develop a computer algebra package for symmetric spaces one needs explicit
formulas expressing the fine structure of the symmetric space and group in terms of each other. In this paper we consider
the case that k is algebraically closed and give explicit algorithmic formulas for expressing the characters of the weight lattice
of the symmetric space in terms of the characters of the weight lattice
of the group. These algorithms can easily be implemented in a computer algebra package.
The root system of the symmetric space
can be described as the image of the root system of the group
under a projection π derived from an involution θ on
. This implies that
. Using these formulas for the characters of each of these lattices we show that in fact
.
A.G. Helminck is partially supported by N.S.F. Grant DMS-0532140. 相似文献
16.
Mark V. Barovich 《Journal of Graph Theory》2000,33(2):55-65
Let G be a 2‐connected graph, let u and v be distinct vertices in V(G), and let X be a set of at most four vertices lying on a common (u, v)‐path in G. If deg(x) ≥ d for all x ∈ V(G) \ {u, v}, then there is a (u, v)‐path P in G with X ⊂ V(P) and |E(P)| ≥ d. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 55–65, 2000 相似文献
17.
In this paper we study tight lower bounds on the size of a maximum matching in a regular graph. For k ≥3, let G be a connected k-regular graph of order n and let α′(G) be the size of a maximum matching in G. We show that if k is even, then
, while if k is odd, then
. We show that both bounds are tight.
Research supported in part by the South African National Research Foundation and the University of KwaZulu-Natal. 相似文献
18.
Tomohiro Uchiyama 《代数通讯》2017,45(11):4833-4845
Let k be a separably closed field. Let G be a reductive algebraic k-group. We study Serre’s notion of complete reducibility of subgroups of G over k. In particular, using the recently proved center conjecture of Tits, we show that the centralizer of a k-subgroup H of G is G-completely reducible over k if it is reductive and H is G-completely reducible over k. We show that a regular reductive k-subgroup of G is G-completely reducible over k. We present examples where the number of overgroups of irreducible subgroups and the number of G(k)-conjugacy classes of k-anisotropic unipotent elements are infinite. 相似文献
19.
LetA be a finite dimensional commutative semisimple algebra over a fieldk and letV be a finitely generatedA-module. We examine the action of the general linear group GL
A
(V) on the set of flags ofk-subspaces ofV. Also, let (V, B) be a finitely generated symplectic module overA. We also investigate the action of the symplectic group Sp
A
(V, B) on the set of flags ofB-isotropick-subspaces ofV, whereB=°B is thek-symplectic form induced by a nonzerok-linear map :A k. In both cases, the orbits are completely classified in terms of certain integer invariants provided that dim
k A=2.This work is partially supported by a KOSEF research grant. 相似文献
20.