共查询到20条相似文献,搜索用时 15 毫秒
1.
INFINITECIRCULANTSANDTHEIRPROPERTIESZHANGFUJI(张福基)HUANGQIONGXIANG(黄琼湘)(DepartmentofMathematics,XinjiangUniversity,Urumchi8300... 相似文献
2.
We raise the following general problem: Which structural properties of dominating subgraphs in finite graphs remain valid for infinite graphs? Positive and negative results are presented. 相似文献
3.
4.
Drago Bokal 《Journal of Graph Theory》2010,65(2):139-162
?iráň constructed infinite families of k‐crossing‐critical graphs for every k?3 and Kochol constructed such families of simple graphs for every k?2. Richter and Thomassen argued that, for any given k?1 and r?6, there are only finitely many simple k‐crossing‐critical graphs with minimum degree r. Salazar observed that the same argument implies such a conclusion for simple k‐crossing‐critical graphs of prescribed average degree r>6. He established the existence of infinite families of simple k‐crossing‐critical graphs with any prescribed rational average degree r∈[4, 6) for infinitely many k and asked about their existence for r∈(3, 4). The question was partially settled by Pinontoan and Richter, who answered it positively for $r\in(3\frac{1}{2},4)$. The present contribution uses two new constructions of crossing‐critical simple graphs along with the one developed by Pinontoan and Richter to unify these results and to answer Salazar's question by the following statement: there exist infinite families of simple k‐crossing‐critical graphs with any prescribed average degree r∈(3, 6), for any k greater than some lower bound Nr. Moreover, a universal lower bound NI on k applies for rational numbers in any closed interval I?(3, 6). © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 139–162, 2010 相似文献
5.
We prove several Helly-type theorems for infinite families of geodesically convex sets in infinite graphs. That is, we determine the least cardinal n such that any family of (particular) convex sets in some infinite graph has a nonempty intersection whenever each of its subfamilies of cardinality less than n has a nonempty intersection. We obtain some general compactness theorems, and some particular results for pseudo-modular graphs, strongly dismantlable graphs and ball-Helly graphs. 相似文献
6.
For any associative unital ring R we investigate two rings – the ring of all infinite upper triangular matrices and the ring of all infinite matrices with the finite number of nonzero entries in each column. We describe derivations of these rings. We prove that every derivation of any of them is a sum of an inner derivation and a derivation which is induced by some derivation of R. 相似文献
7.
It is proved that if ℱ is a family of nine pairwise disjoint compact convex sets in the plane such that no member of ℱ is
contained in the convex hull of the union of two other sets of ℱ, then ℱ has a subfamily ℱ′ with five elements such that no
member of ℱ′ is contained in the convex hull of the union of the other sets of ℱ′. 相似文献
8.
Summary In 1967, Chartrand and Harary characterized finite outer-planar graphs, and Wagner studied uncountable graphs admitting a
planar embedding. We continue this research for those outer-S graphs in surfaces S by studying uncountable graphs admitting S-embeddings with all their vertices in the same face (namely, outer-S embeddings). 相似文献
9.
10.
11.
12.
For a fixed setI of positive integers we consider the set of paths (p
o,...,p
k
) of arbitrary length satisfyingp
l
–p
l–1I forl=2,...,k andp
0=1,p
k
=n. Equipping it with the uniform distribution, the random path lengthT
n
is studied. Asymptotic expansions of the moments ofT
n
are derived and its asymptotic normality is proved. The step lengthsp
l
–p
l–1 are seen to follow asymptotically a restricted geometrical distribution. Analogous results are given for the free boundary case in which the values ofp
0 andp
k
are not specified. In the special caseI={m+1,m+2,...} (for some fixed m) we derive the exact distribution of a random m-gap subset of {1,...,n} and exhibit some connections to the theory of representations of natural numbers. A simple mechanism for generating a randomm-gap subset is also presented. 相似文献
13.
The well-known theorem of Erd?s-Pósa says that a graph G has either k disjoint cycles or a vertex set X of order at most f(k) for some function f such that G\X is a forest. Starting with this result, there are many results concerning packing and covering cycles in graph theory and combinatorial optimization. In this paper, we discuss packing disjoint S-cycles, i.e., cycles that are required to go through a set S of vertices. For this problem, Kakimura-Kawarabayashi-Marx (2011) and Pontecorvi-Wollan (2010) recently showed the Erd?s-Pósa-type result holds. We further try to generalize this result to packing S-cycles of odd length. In contrast to packing S-cycles, the Erd?s-Pósa-type result does not hold for packing odd S-cycles. We then relax packing odd S-cycles to half-integral packing, and show the Erd?s-Pósa-type result for the half-integral packing of odd S-cycles, which is a generalization of Reed (1999) when S=V. That is, we show that given an integer k and a vertex set S, a graph G has either 2k odd S-cycles so that each vertex is in at most two of these cycles, or a vertex set X of order at most f(k) (for some function f) such that G\X has no odd S-cycle. 相似文献
15.
Julien Moncel 《Designs, Codes and Cryptography》2006,41(1):23-31
For all t ≥ 2, we give an explicit construction of an infinite family of graphs such that G admits a code identifying sets of at most t vertices of G of cardinality O(t
2 ln |V(G)|) for all members G of the family. This beats the best previously known explicit construction by a factor of t
2.
相似文献
16.
We present a planar hypohamiltonian graph on 48 vertices, and derive some consequences. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 338–342, 2007 相似文献
17.
Marc Chastand 《Discrete Mathematics》2006,306(16):1846-1861
We prove that the vertex set of a Kℵ0-free weakly median graph G endowed with the weak topology associated with the geodesic convexity on V(G) is compact if and only if G has one of the following equivalent properties: (1) G contains no isometric rays; (2) any chain of interval of G ordered by inclusion is finite; (3) every self-contraction of G fixes a non-empty finite regular weakly median subgraph of G. We study the self-contractions of Kℵ0-free weakly median graphs which fix no finite set of vertices. We also follow a suggestion of Imrich and Klavzar [Product Graphs, Wiley, New York, 2000] by defining different centers of such a graph G, each of them giving rise to a non-empty finite regular weakly median subgraph of G which is fixed by all automorphisms of G. 相似文献
18.
A. A. Chernyak 《Mathematical Notes》1990,47(4):391-400
Translated from Matematicheskie Zametki, Vol. 47, No. 4, pp. 115–127, April, 1990. 相似文献
19.
In this article, the inverse problem of the differential inclusion theory is studied. For a given ε>0 and a continuous set valued map t→W(t), t∈[t0,θ], where W(t)⊂Rn is compact and convex for every t∈[t0,θ], it is required to define differential inclusion so that the Hausdorff distance between the attainable set of the differential inclusion at the time moment t with initial set (t0,W(t0)) and W(t) would be less than ε for every t∈[t0,θ]. 相似文献
20.
该文利用矩阵测度和Schauder不动点定理研究了具有无穷时滞Volterra型积分微分方程周期解的存在性、唯一性及一致稳定性, 获得了一些判别准则, 推广和改进了有关的结果. 相似文献