首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 31 毫秒
1.
Different partial hypergroupoids are associated with binary relations defined on a set H. In this paper we find sufficient and necessary conditions for these hypergroupoids in order to be reduced hypergroups. Given two binary relations ρ and σ on H we investigate when the hypergroups associated with the relations ρσ, ρσ and ρσ are reduced. We also determine when the cartesian product of two hypergroupoids associated with a binary relation is a reduced hypergroup.  相似文献   

2.
A class of constrained nonsmooth convex optimization problems, that is, piecewise C2 convex objectives with smooth convex inequality constraints are transformed into unconstrained nonsmooth convex programs with the help of exact penalty function. The objective functions of these unconstrained programs are particular cases of functions with primal-dual gradient structure which has connection with VU space decomposition. Then a VU space decomposition method for solving this unconstrained program is presented. This method is proved to converge with local superlinear rate under certain assumptions. An illustrative example is given to show how this method works.  相似文献   

3.
Let a normed space X possess a tiling T consisting of unit balls. We show that any packing P of X obtained by a small perturbation of T is completely translatively saturated; that is, one cannot replace finitely many elements of P by a larger number of unit balls such that the resulting arrangement is still a packing.In contrast with that, given a tiling T of Rn with images of a convex body C under Euclidean isometries, there may exist packings P consisting of isometric images of C obtained from T by arbitrarily small perturbations which are no longer completely saturated. This means that there exists some positive integer k such that one can replace k−1 members of P by k isometric copies of C without violating the packing property. However, we quantify a tradeoff between the size of the perturbation and the minimal k such that the above phenomenon occurs.Analogous results are obtained for coverings.  相似文献   

4.
We obtain new fixed point theorems on multimaps in the class Bp defined on almost convex subsets of topological vector spaces. Our main results are applied to deduce various fixed point theorems, coincidence theorems, almost fixed point theorems, intersection theorems, and minimax theorems. Consequently, our new results generalize well-known works of Kakutani, Fan, Browder, Himmelberg, Lassonde, and others.  相似文献   

5.
In this paper, we prove that strongly convex space and almost locally uniformly rotund space, very convex space and weakly almost locally uniformly rotund space are respectively equivalent. We also investigate a few properties of k-strongly convex space and k-very convex space, and discuss the applications of strongly convex space and very convex space in approximation theory.  相似文献   

6.
We describe a connection between the combinatorics of generators for certain groups and the combinatorics of Helly's 1913 theorem on convex sets. We use this connection to prove fixed point theorems for actions of these groups on nonpositively curved metric spaces. These results are encoded in a property that we introduce called “property FAr”, which reduces to Serre's property FA when r=1. The method applies to S-arithmetic groups in higher Q-rank, to simplex reflection groups (including some nonarithmetic ones), and to higher rank Chevalley groups over polynomial and other rings (for example SLn(Z[x1,…,xd]), n>2).  相似文献   

7.
Let m be a positive integer and let G be a graph. We consider the question: can the edge set E(G) of G be expressed as the union of a set M of matchings of G each of which has size exactly m? If this happens, we say that G is [m]-coverable and we call M an [m]-covering of G. It is interesting to consider minimum[m]-coverings, i.e. [m]-coverings containing as few matchings as possible. Such [m]-coverings will be called excessive[m]-factorizations. The number of matchings in an excessive [m]-factorization is a graph parameter which will be called the excessive[m]-index and denoted by . In this paper we begin the study of this new parameter as well as of a number of other related graph parameters.  相似文献   

8.
Using results by McKee and Woodall on binary matroids, we show that the set of postman sets has odd cardinality, generalizing a result by Toida on the cardinality of cycles in Eulerian graphs. We study the relationship between T-joins and blocks of the underlying graph, obtaining a decomposition of postman sets in terms of blocks. We conclude by giving several characterizations of T-joins which are postman sets.  相似文献   

9.
S. Mishra  S.B. Rao 《Discrete Mathematics》2006,306(14):1586-1594
In this paper we consider a graph optimization problem called minimum monopoly problem, in which it is required to find a minimum cardinality set SV, such that, for each uV, |N[u]∩S|?|N[u]|/2 in a given graph G=(V,E). We show that this optimization problem does not have a polynomial-time approximation scheme for k-regular graphs (k?5), unless P=NP. We show this by establishing two L-reductions (an approximation preserving reduction) from minimum dominating set problem for k-regular graphs to minimum monopoly problem for 2k-regular graphs and to minimum monopoly problem for (2k-1)-regular graphs, where k?3. We also show that, for tree graphs, a minimum monopoly set can be computed in linear time.  相似文献   

10.
We show that for any positive integer k?4, if R is a (2k-1)×(2k-1) partial Latin square, then R is avoidable given that R contains an empty row, thus extending a theorem of Chetwynd and Rhodes. We also present the idea of avoidability in the setting of partial r-multi Latin squares, and give some partial fillings which are avoidable. In particular, we show that if R contains at most nr/2 symbols and if there is an n×n Latin square L such that δn of the symbols in L cover the filled cells in R where 0<δ<1, then R is avoidable provided r is large enough.  相似文献   

11.
We give a decomposition formula for the determinant on the bond scattering matrix of a regular covering of G. Furthermore, we define an L-function of G, and give a determinant expression of it. As a corollary, we express the determinant on the bond scattering matrix of a regular covering of G by means of its L-functions.  相似文献   

12.
Let G be a graph of order n and S be a vertex set of q vertices. We call G,S-pancyclable, if for every integer i with 3≤iq there exists a cycle C in G such that |V(C)∩S|=i. For any two nonadjacent vertices u,v of S, we say that u,v are of distance two in S, denoted by dS(u,v)=2, if there is a path P in G connecting u and v such that |V(P)∩S|≤3. In this paper, we will prove that if G is 2-connected and for all pairs of vertices u,v of S with dS(u,v)=2, , then there is a cycle in G containing all the vertices of S. Furthermore, if for all pairs of vertices u,v of S with dS(u,v)=2, , then G is S-pancyclable unless the subgraph induced by S is in a class of special graphs. This generalizes a result of Fan [G. Fan, New sufficient conditions for cycles in graphs, J. Combin. Theory B 37 (1984) 221-227] for the case when S=V(G).  相似文献   

13.
We give the Ramsey number for a disjoint union of some G-good graphs versus a graph G generalizing the results of Stahl (1975) [5] and Baskoro et al. (2006) [1] and the previous result of the author Bielak (2009) [2]. Moreover, a family of G-good graphs with s(G)>1 is presented.  相似文献   

14.
Pavol Hell 《Discrete Mathematics》2009,309(18):5703-5373
A sequence 〈d1,d2,…,dn〉 of non-negative integers is graphical if it is the degree sequence of some graph, that is, there exists a graph G on n vertices whose ith vertex has degree di, for 1≤in. The notion of a graphical sequence has a natural reformulation and generalization in terms of factors of complete graphs.If H=(V,E) is a graph and g and f are integer-valued functions on the vertex set V, then a (g,f)-factor of H is a subgraph G=(V,F) of H whose degree at each vertex vV lies in the interval [g(v),f(v)]. Thus, a (0,1)-factor is just a matching of H and a (1, 1)-factor is a perfect matching of H. If H is complete then a (g,f)-factor realizes a degree sequence that is consistent with the sequence of intervals 〈[g(v1),f(v1)],[g(v2),f(v2)],…,[g(vn),f(vn)]〉.Graphical sequences have been extensively studied and admit several elegant characterizations. We are interested in extending these characterizations to non-graphical sequences by introducing a natural measure of “near-graphical”. We do this in the context of minimally deficient (g,f)-factors of complete graphs. Our main result is a simple linear-time greedy algorithm for constructing minimally deficient (g,f)-factors in complete graphs that generalizes the method of Hakimi and Havel (for constructing (f,f)-factors in complete graphs, when possible). It has the added advantage of producing a certificate of minimum deficiency (through a generalization of the Erdös-Gallai characterization of (f,f)-factors in complete graphs) at no additional cost.  相似文献   

15.
A graph G is 2-stratified if its vertex set is partitioned into two nonempty classes (each of which is a stratum or a color class). We color the vertices in one color class red and the other color class blue. Let F be a 2-stratified graph with one fixed blue vertex v specified. We say that F is rooted at v. The F-domination number of a graph G is the minimum number of red vertices of G in a red-blue coloring of the vertices of G such that for every blue vertex v of G, there is a copy of F in G rooted at v. In this paper, we survey recent results on the F-domination number for various 2-stratified graphs F.  相似文献   

16.
In this paper we study (4,2μ)-GDDs of type gn possessing both the pan-decomposable property introduced by Granville, Moisiadis, Rees, On complementary decompositions of the complete graph, Graphs and Combinatorics 5 (1989) 57-61 and the pan-orientable property introduced by Grüttmüller, Hartmann, Pan-orientable block designs, Australas. J. Combin. 40 (2008) 57-68. We show that the necessary condition for a (4,2μ)-GDD satisfying both of these properties, namely (1) n≥4, μg(n−1)≡0 (mod 3), and (2) g−1,n are not both even if μ is odd are sufficient. When λ=2, our designs are super-simple.We also determine the spectrum of (4,2)-GDDs which are super-simple and possess some of the decomposable/orientable conditions, but are not pan-decomposable or pan-orientable. In particular, we show that the necessary conditions for a super-simple directable (4,2)-GDD of type gn are sufficient.  相似文献   

17.
Let G=(V,E) be a finite, simple and non-empty (p,q)-graph of order p and size q. An (a,d)-vertex-antimagic total labeling is a bijection f from V(G)∪E(G) onto the set of consecutive integers 1,2,…,p+q, such that the vertex-weights form an arithmetic progression with the initial term a and the common difference d, where the vertex-weight of x is the sum of values f(xy) assigned to all edges xy incident to vertex x together with the value assigned to x itself, i.e. f(x). Such a labeling is called super if the smallest possible labels appear on the vertices.In this paper, we will study the properties of such labelings and examine their existence for disconnected graphs.  相似文献   

18.
Maria Monks 《Discrete Mathematics》2009,309(16):5196-1883
All continuous endomorphisms f of the shift dynamical system S on the 2-adic integers Z2 are induced by some , where n is a positive integer, Bn is the set of n-blocks over {0, 1}, and f(x)=y0y1y2… where for all iN, yi=f(xixi+1xi+n−1). Define D:Z2Z2 to be the endomorphism of S induced by the map {(00,0),(01,1),(10,1),(11,0)} and V:Z2Z2 by V(x)=−1−x. We prove that D, V°D, S, and V°S are conjugate to S and are the only continuous endomorphisms of S whose parity vector function is solenoidal. We investigate the properties of D as a dynamical system, and use D to construct a conjugacy from the 3x+1 function T:Z2Z2 to a parity-neutral dynamical system. We also construct a conjugacy R from D to T. We apply these results to establish that, in order to prove the 3x+1 conjecture, it suffices to show that for any mZ+, there exists some nN such that R−1(m) has binary representation of the form or .  相似文献   

19.
We introduce a new type of the Bartholdi zeta function of a digraph D. Furthermore, we define a new type of the Bartholdi L-function of D, and give a determinant expression of it. We show that this L-function of D is equal to the L-function of D defined in [H. Mizuno, I. Sato, A new Bartholdi zeta function of a digraph, Linear Algebra Appl. 423 (2007) 498-511]. As a corollary, we obtain a decomposition formula for a new type of the Bartholdi zeta function of a group covering of D by new Bartholdi L-functions of D.  相似文献   

20.
Recently Alon and Friedland have shown that graphs which are the union of complete regular bipartite graphs have the maximum number of 1-factors over all graphs with the same degree sequence. We identify two families of graphs that have the maximum number of 1-factors over all graphs with the same number of vertices and edges: the almost regular graphs which are unions of complete regular bipartite graphs, and complete graphs with a matching removed. The first family is determined using the Alon and Friedland bound. For the second family, we show that a graph transformation which is known to increase network reliability also increases the number of 1-factors. In fact, more is true: this graph transformation increases the number of k-factors for all k≥1, and “in reverse” also shows that in general, threshold graphs have the fewest k-factors. We are then able to determine precisely which threshold graphs have the fewest 1-factors. We conjecture that the same graphs have the fewest k-factors for all k≥2 as well.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号