共查询到20条相似文献,搜索用时 453 毫秒
1.
William Kocay 《Graphs and Combinatorics》1992,8(3):259-276
LetV be a set ofn elements. The set of allk-subsets ofV is denoted
. Ak-hypergraph G consists of avertex-set V(G) and anedgeset
, wherek≥2. IfG is a 3-hypergraph, then the set of edges containing a given vertexvεV(G) define a graphG
v
. The graphs {G
v
νvεV(G)} aresubsumed byG. Each subsumed graphG
v
is a graph with vertex-setV(G) − v. They can form the set of vertex-deleted subgraphs of a graphH, that is, eachG
v
≽H −v, whereV(H)=V(G). In this case,G is a hypergraphic reconstruction ofH. We show that certain families of self-complementary graphsH can be reconstructed in this way by a hypergraphG, and thatG can be extended to a hypergraphG
*, all of whose subsumed graphs are isomorphic toH, whereG andG
* are self-complementary hypergraphs. In particular, the Paley graphs can be reconstructed in this way.
This work was supported by an operating grant from the Natural Sciences and Engineering Research Council of Canada. 相似文献
2.
A 4-semiregular 1-factorization is a 1-factorization in which every pair of distinct 1-factors forms a union of 4-cycles. LetK be the complete graphK
2nor the complete bipartite graphK
n, n
.We prove that there is a 4-semiregular 1-factorization ofK if and only ifn is a power of 2 andn2, and 4-semiregular 1-factorizations ofK are isomorphic, and then we determine the symmetry groups. They are known for the case of the complete graphK
2n
,however, we prove them in a different method. 相似文献
3.
Onur Yavuz 《Integral Equations and Operator Theory》2007,58(3):433-446
We consider a multiply connected domain
where
denotes the unit disk and
denotes the closed disk centered at
with radius r
j
for j = 1, . . . , n. We show that if T is a bounded linear operator on a Banach space X whose spectrum contains ∂Ω and does not contain the points λ1, λ2, . . . , λ
n
, and the operators T and r
j
(T − λ
j
I)−1 are polynomially bounded, then there exists a nontrivial common invariant subspace for T
* and (T − λ
j
I)*-1. 相似文献
4.
Packing 4-Cycles in Eulerian and Bipartite Eulerian Tournaments with an Application to Distances in Interchange Graphs 总被引:1,自引:0,他引:1
Raphael Yuster 《Annals of Combinatorics》2005,9(1):117-124
We prove that every Eulerian orientation of Km,n contains
arc-disjoint directed 4-cycles, improving earlier lower bounds. Combined with a probabilistic argument, this result is used to prove that every regular tournament with n vertices contains
arc-disjoint directed 4-cycles. The result is also used to provide an upper bound for the distance between two antipodal vertices in interchange graphs.Received February 6, 2004 相似文献
5.
In this paper, a natural R
+
n+1
extension of singular integrals, i.e.,T
κ:f→K*φ
t
*t with K a standard C-Z kernel and ϕ usual one, is investigated. One of the main results is: Let (dμ, udx) ∈C1 and u-Mw, w∈A∞, then Tk is of type (Lp(udx), Lp(dμ)). As a related topic, a maximal operator
is proved to be of type
, where
, provided (dμ, udx) ∈C1 and u∈ A∞.
Supported by National Science Foundation of China 相似文献
6.
In 2-edge-colored graphs, we define an (s, t)-cycle to be a cyle of length s + t, in which s consecutive edges are in one color and the remaining t edges are in the other color. Here we investigate the existence of (s, t)-cycles, in a 2-edge-colored complete graph Kcn on n vertices. In particular, in the first result we give a complete characterization for the existence of (s, t)-cycles in Kcn with n relatively large with respect to max({s, t}). We also study cycles of length 4 for all possible values of s and t. Then, we show that Kcn contains an (s, t)-hamiltonian cycle unless it is isomorphic to a specified graph. This extends a result of A. Gyárfás [Journal of Graph Theory, 7 (1983), 131–135]. Finally, we give some sufficient conditions for the existence of (s, 1)-cycles, (inverted sans serif aye) s ϵ {2, 3,…, n − 2}. © 1996 John Wiley & Sons, Inc. 相似文献
7.
Summary AK
4–e design of ordern is a pair (S, B), whereB is an edge-disjoint decomposition ofK
n (the complete undirected graph onn vertices) with vertex setS, into copies ofK
4–e, the graph on four vertices with five edges. It is well-known [1] thatK
4–e designs of ordern exist for alln 0 or 1 (mod 5),n 6, and that if (S, B) is aK
4–e design of ordern then |B| =n(n – 1)/10.Asimple covering ofK
n with copies ofK
4–e is a pair (S, C) whereS is the vertex set ofK
n andC is a collection of edge-disjoint copies ofK
4–e which partitionE(Kn)P, for some
. Asimple minimum covering ofK
n (SMCK
n) with copies ofK
4–e is a simple covering whereP consists of as few edges as possible. The collection of edgesP is called thepadding. Thus aK
4–e design of ordern isSMCK
n with empty padding.We show that forn 3 or 8 (mod 10),n 8, the padding ofSMCK
n consists of two edges and that forn 2, 4, 7 or 9 (mod 10),n 9, the padding consists of four edges. In each case, the padding may be any of the simple graphs with two or four edges respectively. The smaller cases need separate treatment:SMCK
5 has four possible paddings of five edges each,SMCK
4 has two possible paddings of four edges each andSMCK
7 has eight possible paddings of four edges each.The recursive arguments depend on two essential ingredients. One is aK
4–e design of ordern with ahole of sizek. This is a triple (S, H, B) whereB is an edge-disjoint collection of copies ofK
4–e which partition the edge set ofK
n\Kk, whereS is the vertex set ofK
n, and
is the vertex set ofK
k. The other essential is acommutative quasigroup with holes. Here we letX be a set of size 2n 6, and letX = {x
1, x2, ..., xn} be a partition ofX into 2-element subsets, calledholes of size two. Then a commutative quasigroup with holesX is a commutative quasigroup (X, ) such that for each holex
i X, (xi, ) is a subquasigroup. Such quasigroups exist for every even order 2n 6 [4]. 相似文献
8.
Consider the parameter space Θ which is an open subset of ℝ
k
,k≧1, and for each θ∈Θ, let the r.v.′sY
n
,n=0, 1, ... be defined on the probability space (X,A,P
θ) and take values in a Borel setS of a Euclidean space. It is assumed that the process {Y
n
},n≧0, is Markovian satisfying certain suitable regularity conditions. For eachn≧1, let υ
n
be a stopping time defined on this process and have some desirable properties. For 0 < τ
n
→ ∞ asn→∞, set
h
n
→h ∈R
k
, and consider the log-likelihood function
of the probability measure
with respect to the probability measure
. Here
is the restriction ofP
θ to the σ-field induced by the r.v.′sY
0,Y
1, ...,
. The main purpose of this paper is to obtain an asymptotic expansion of
in the probability sense. The asymptotic distribution of
, as well as that of another r.v. closely related to it, is obtained under both
and
.
This research was supported by the National Science Foundation, Grant MCS77-09574.
Research supported by the National Science Foundation, Grant MCS76-11620. 相似文献
9.
We prove inequalities about the quermassintegralsV
k
(K) of a convex bodyK in ℝ
n
(here,V
k
(K) is the mixed volumeV((K, k), (B
n
,n − k)) whereB
n
is the Euclidean unit ball). (i) The inequality
holds for every pair of convex bodiesK andL in ℝ
n
if and only ifk=2 ork=1. (ii) Let 0≤k≤p≤n. Then, for everyp-dimensional subspaceE of ℝ
n
,
whereP
E
K denotes the orthogonal projection ofK ontoE. The proof is based on a sharp upper estimate for the volume ratio |K|/|L| in terms ofV
n−k
(K)/V
n−k
(L), wheneverL andK are two convex bodies in ℝ
n
such thatK ⊆L. 相似文献
10.
Zbigniew Lonc 《Graphs and Combinatorics》1992,8(4):333-341
Anh-uniform hypergraph generated by a set of edges {E
1,...,E
c} is said to be a delta-system Δ(p,h,c) if there is ap-element setF such that ∇F|=p andE
i⌢E
j=F,∀i≠j.
The main result of this paper says that givenp, h andc, there isn
0 such that forn≥n
0 the set of edges of a completeh-uniform hypergraphK
n
h can be partitioned into subsets generating isomorphic delta-systems Δ(p, h, c) if and only if
. This result is derived from a more general theorem in which the maximum number of delta-systems Δ(p, h, c) that can be packed intoK
n
h and the minimum number of delta-systems Δ(p, h, c) that can cover the edges ofK
n
h are determined for largen. Moreover, we prove a theorem on partitioning of the edge set ofK
n
h into subsets generating small but not necessarily isomorphic delta-systems. 相似文献
11.
Andreas Huck 《Graphs and Combinatorics》1991,7(4):323-351
We consider graphs, which are finite, undirected, without loops and in which multiple edges are possible. For each natural numberk letg(k) be the smallest natural numbern, so that the following holds:LetG be ann-edge-connected graph and lets
1,...,s
k,t
1,...,t
k be vertices ofG. Then for everyi {1,..., k} there existsa pathP
i froms
i tot
i, so thatP
1,...,P
k are pairwise edge-disjoint. We prove
相似文献
12.
Ioan Tomescu 《Random Structures and Algorithms》1994,5(1):205-213
In this article it is shown that the number of common edges of two random subtrees of Kn having r and s vertices, respectively, has a Poisson distribution with expectation 2λμ if $\mathop {\lim }\limits_{n \to \infty } r/n = \lambda$ and $\mathop {\lim }\limits_{n \to \infty } s/n = \mu$. Also, some estimations of the number of subtrees for almost all graphs are made by using Chebycheff's inequality. © 1994 John Wiley & Sons, Inc. 相似文献
13.
James E. Williamson 《Periodica Mathematica Hungarica》1977,8(2):105-116
A graphG of orderp is said to bepanconnected if for each pairu, v of vertices ofG, there exists a,u, v-path of lengthl inG, for eachl such that dG(u, v)lp – 1, whered
G
(u, v) denotes the length of a shortestu, v-path inG. Three conditions are shown to be sufficient for a graphG of orderp to be panconnected: (1) the degree of each vertex ofG is at least (p+2)/2; (2) the sum of the degrees of each pair of nonadjacent vertices ofG is at least (3p–2)/2; (3) the graphG has at least
edges. It is also shown that each of these conditions is best possible. Additional results on panconnectedness are obtained including a characterization of those completen-partite graphs which are panconnected. 相似文献
14.
Ryan B. Hayward 《Discrete and Computational Geometry》1987,2(1):327-343
Consider a drawing in the plane ofK
n
, the complete graph onn vertices. If all edges are restricted to be straight line segments, the drawing is called rectilinear. Consider a Hamiltonian cycle in a drawing ofK
n
. If no pair of the edges of the cycle cross, it is called a crossing-free Hamiltonian cycle (cfhc). Let (n) represent the maximum number of cfhc's of any drawing ofK
n
, and
(n) the maximum number of cfhc's of any rectilinear drawing ofK
n
. The problem of determining (n) and
(n), and determining which drawings have this many cfhc's, is known as the optimal cfhc problem. We present a brief survey of recent work on this problem, and then, employing a recursive counting argument based on computer enumeration, we establish a substantially improved lower bound for (n) and
(n). In particular, it is shown that
(n) is at leastk × 3.2684
n
. We conjecture that both (n) and
(n) are at mostc × 4.5
n
.This research, part of which was conducted at Queen's University, was supported by an N.S.E.R.C. postgraduate scholarship. 相似文献
15.
Peter Hermann 《manuscripta mathematica》1995,88(1):1-24
The principal goal of this paper is to investigate the representation theory of double coset hypergroups. IfK=G//H is a double coset hypergroup, representations ofK can canonically be obtained from those ofG. However, not every representation ofK originates from this construction in general, i.e., extends to a representation ofG. Properties of this construction are discussed, and as the main result it turns out that extending representations ofK is compatible with the inducing process (as introduced in [7]). It follows that a representation weakly contained in the
left-regular representation ofK always admits an extension toG. Furthermore, we realize the Gelfand pair
(where
are a local field andR its ring of integers) as a polynomial hypergroup on ℕ0 and characterize the (proper) subset of its dual consisting of extensible representations. 相似文献
16.
We study the smallest number ψ(K) such that a given convex bodyK in ℝ
n
can be cut into two partsK
1 andK
2 by a surface with an (n−1)-dimensional measure ψ(K) vol(K
1)·vol(K
2)/vol(K). LetM
1(K) be the average distance of a point ofK from its center of gravity. We prove for the “isoperimetric coefficient” that
相似文献
17.
A subgroup H of a finite group G is said to be c*-supplemented in G if there exists a subgroup K such that G = HK and H ⋂ K is permutable in G. It is proved that a finite group G that is S
4-free is p-nilpotent if N
G
(P) is p-nilpotent and, for all x ∈ G\N
G
(P), every minimal subgroup of
is c*-supplemented in P and (if p = 2) one of the following conditions is satisfied: (a) every cyclic subgroup of
of order 4 is c*-supplemented in P, (b)
, (c) P is quaternion-free, where P a Sylow p-subgroup of G and
is the p-nilpotent residual of G. This extends and improves some known results.
Published in Ukrains’kyi Matematychnyi Zhurnal, Vol. 59, No. 8, pp. 1011–1019, August, 2007. 相似文献
18.
Let K be an infinite field with characteristic different from two and (K) the n-sphere over K. We show that ambient polynomial automorphisms of (K) preserve the quadratic form x
02 + ⋯ + x
n
2 and the group Aut ((K
n+1, (K)) of such automorphisms of (K) is isomorphic to the (n + 1)-orthogonal group O(n + 1, K) provided K is real.
Next, the restriction map Aut (K
3, (K)) → Aut ( (K)) yields a surjection provided K is an algebraically closed field as well. Furthermore, for any such a field K, there is an imbedding
19.
Paweł Hitczenko 《Israel Journal of Mathematics》1993,84(1-2):161-178
Letf
n
= Σ
k=1
n
v
k
r
k
,n=1,…, be a martingale transform of a Rademacher sequence (r
n)and let (r
n
′
) be an independent copy of (r
n).The main result of this paper states that there exists an absolute constantK such that for allp, 1≤p<∞, the following inequality is true:
In order to prove this result, we obtain some inequalities which may be of independent interest. In particular, we show that
for every sequence of scalars (a
n)one has
where
is theK-interpolation norm between ℓ1 and ℓ2. We also derive a new exponential inequality for martingale transforms of a Rademacher sequence.
This research was supported in part by an NSF grant and an FRPD grant at NCSU. 相似文献
20.
Let G be a graph with n vertices, m edges and a vertex degree sequence (d
1, d
2,..., d
n
), where d
1 ≥ d
2 ≥ ... ≥ d
n
. The spectral radius and the largest Laplacian eigenvalue are denoted by ϱ(G) and μ(G), respectively. We determine the graphs with
|