共查询到20条相似文献,搜索用时 31 毫秒
1.
Y. Boudabbous 《Discrete Mathematics》2009,309(9):2839-2846
Given a directed graph G=(V,A), the induced subgraph of G by a subset X of V is denoted by G[X]. A subset X of V is an interval of G provided that for a,b∈X and x∈V?X, (a,x)∈A if and only if (b,x)∈A, and similarly for (x,a) and (x,b). For instance, 0?, V and {x}, x∈V, are intervals of G, called trivial intervals. A directed graph is indecomposable if all its intervals are trivial, otherwise it is decomposable. Given an indecomposable directed graph G=(V,A), a vertex x of G is critical if G[V?{x}] is decomposable. An indecomposable directed graph is critical when all its vertices are critical. With each indecomposable directed graph G=(V,A) is associated its indecomposability directed graph defined on V by: given x≠y∈V, (x,y) is an arc of if G[V?{x,y}] is indecomposable. All the results follow from the study of the connected components of the indecomposability directed graph. First, we prove: if G is an indecomposable directed graph, which admits at least two non critical vertices, then there is x∈V such that G[V?{x}] is indecomposable and non critical. Second, we characterize the indecomposable directed graphs G which have a unique non critical vertex x and such that G[V?{x}] is critical. Third, we propose a new approach to characterize the critical directed graphs. 相似文献
2.
Houcine Bouchaala 《Comptes Rendus Mathematique》2004,338(2):109-112
A tournament T=(V,A) is a directed graph such that for every x,y∈V, where x≠y, (x,y)∈A if and only if (y,x)?A. For example, the 3-cycle is the tournament ({1,2,3}, {(1,2),(2,3),(3,1)}). Up to an isomorphism, there are two tournaments with 4 vertices and containing an unique 3-cycle which we call diamonds. We prove that for any tournament T defined on n?9 vertices, either T contains at least 2n?6 diamonds or the number of diamonds contained in T is equal to 0, n?3 or 2n?8. Following the characterization of the tournaments without diamonds due to Gnanvo and Ille (Z. Math. Logik Grundlag. Math. 38 (1992) 283–291) and to Lopez and Rauzy (Z. Math. Logik Grundlag. Math. 38 (1992) 27–37), we study the morphology of the tournaments defined on n?5 vertices and which contain exactly n?3 or 2n?8 diamonds. To cite this article: H. Bouchaala, C. R. Acad. Sci. Paris, Ser. I 338 (2004). 相似文献
3.
A. Boussaïri 《Discrete Mathematics》2009,309(10):3404-3407
Given a digraph G=(V,A), the subdigraph of G induced by a subset X of V is denoted by G[X]. With each digraph G=(V,A) is associated its dual G?=(V,A?) defined as follows: for any x,y∈V, (x,y)∈A? if (y,x)∈A. Two digraphs G and H are hemimorphic if G is isomorphic to H or to H?. Given k>0, the digraphs G=(V,A) and H=(V,B) are k-hemimorphic if for every X⊆V, with |X|≤k, G[X] and H[X] are hemimorphic. A class C of digraphs is k-recognizable if every digraph k-hemimorphic to a digraph of C belongs to C. In another vein, given a digraph G=(V,A), a subset X of V is an interval of G provided that for a,b∈X and x∈V−X, (a,x)∈A if and only if (b,x)∈A, and similarly for (x,a) and (x,b). For example, 0?, {x}, where x∈V, and V are intervals called trivial. A digraph is indecomposable if all its intervals are trivial. We characterize the indecomposable digraphs which are 3-hemimorphic to a non-indecomposable digraph. It follows that the class of indecomposable digraphs is 4-recognizable. 相似文献
4.
Chandan K. Dubey 《Discrete Applied Mathematics》2009,157(1):149-163
An undirected graph G=(V,E) with a specific subset X⊂V is called X-critical if G and G(X), induced subgraph on X, are indecomposable but G(V−{w}) is decomposable for every w∈V−X. This is a generalization of critically indecomposable graphs studied by Schmerl and Trotter [J.H. Schmerl, W.T. Trotter, Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures, Discrete Mathematics 113 (1993) 191-205] and Bonizzoni [P. Bonizzoni, Primitive 2-structures with the (n−2)-property, Theoretical Computer Science 132 (1994) 151-178], who deal with the case where X is empty.We present several structural results for this class of graphs and show that in every X-critical graph the vertices of V−X can be partitioned into pairs (a1,b1),(a2,b2),…,(am,bm) such that G(V−{aj1,bj1,…,ajk,bjk}) is also an X-critical graph for arbitrary set of indices {j1,…,jk}. These vertex pairs are called commutative elimination sequence. If G is an arbitrary indecomposable graph with an indecomposable induced subgraph G(X), then the above result establishes the existence of an indecomposability preserving sequence of vertex pairs (x1,y1),…,(xt,yt) such that xi,yi∈V−X. As an application of the commutative elimination sequence of an X-critical graph we present algorithms to extend a 3-coloring (similarly, 1-factor) of G(X) to entire G. 相似文献
5.
A tournament T on any set X is a dyadic relation such that for any x, y ∈ X (a) (x, x) ? T and (b) if x ≠ y then (x, y) ∈ T iff (y, x) ? T. The score vector of T is the cardinal valued function defined by R(x) = |{y ∈ X : (x, y) ∈ T}|. We present theorems for infinite tournaments analogous to Landau's necessary and sufficient conditions that a vector be the score vector for some finite tournament. Included also is a new proof of Landau's theorem based on a simple application of the “marriage” theorem. 相似文献
6.
Conditions are given on maps A, C∈ L(X, V) and B, D ∈ L(Y, V) for which Cx∧Dy = Ax∧By for all x ∈ X and y ∈ Y, and, when X = Y, for which Cx∧Dx = Ax ∧Bx for all x ∈ X. 相似文献
7.
Houmem Belkhechine Imed Boudabbous Kaouthar Hzami 《Comptes Rendus Mathematique》2013,351(13-14):501-504
We consider a tournament . For , the subtournament of T induced by X is . An interval of T is a subset X of V such that, for and , if and only if . The trivial intervals of T are ?, and V. A tournament is indecomposable if all its intervals are trivial. For , denotes the unique indecomposable tournament defined on such that is the usual total order. Given an indecomposable tournament T, denotes the set of such that there is satisfying and is isomorphic to . Latka [6] characterized the indecomposable tournaments T such that . The authors [1] proved that if , then . In this note, we characterize the indecomposable tournaments T such that . 相似文献
8.
A king x in a tournament T is a player who beats any other player y directly (i.e., x→y) or indirectly through a third player z (i.e., x→z and z→y). For x,y∈V(T), let b(x,y) denote the number of third players through which x beats y indirectly. Then, a king x is strong if the following condition is fulfilled: b(x,y)>b(y,x) whenever y→x. In this paper, a result shows that for a tournament on n players there exist exactly k strong kings, 1?k?n, with the following exceptions: k=n-1 when n is odd and k=n when n is even. Moreover, we completely determine the uniqueness of tournaments. 相似文献
9.
David C. Fisher David Guichard J. Richard Lundgren Sarah K. Merz K. Brooks Reid 《Graphs and Combinatorics》2001,17(2):227-236
A tournament is an oriented complete graph. Vertices x and y dominate a tournament T if for all vertices z≠x,y, either (x,z) or (y,z) are arcs in T (possibly both). The domination graph of a tournament T is the graph on the vertex set of T containing edge {x,y} if and only if x and y dominate T. In this paper we determine which graphs containing no isolated vertices are domination graphs of tournaments.
Received: May 20, 1998 Final version received: May 26, 1999 相似文献
10.
P.S Milojević 《Journal of Mathematical Analysis and Applications》1978,65(2):468-502
Let X and Y be real normed spaces with an admissible scheme Γ = {En, Vn; Fn, Wn} and T: X → 2YA-proper with respect to Γ such that dist(y, A(x)) < kc(∥ x ∥) for all y in T(x) with ∥ x ∥ ? R for some R > 0 and k > 0, where c: R+ → R+ is a given function and A: X → 2Y a suitable possibly not A-proper mapping. Under the assumption that either T or A is odd or that (u, Kx) ? 0 for all u in T(x) with , we obtain (in a constructive way) various generalizations of the first Fredholm theorem. The unique approximation-solvability results for the equation T(x) = f with T such that T(x) ? T(y) ?A(x ? y) for x, y in X or T is Fréchet differentiable are also established. The abstract results for A-proper mappings are then applied to the (constructive) solvability of some boundary value problems for quasilinear elliptic equations. Some of our results include the results of Lasota, Lasota-Opial, Hess, Ne?as, Petryshyn, and Babu?ka. 相似文献
11.
12.
Let A=(aij) be a real symmetric matrix of order n. We characterize all nonnegative vectors x=(x1,...,xn) and y=(y1,...,yn) such that any real symmetric matrix B=(bij), with bij=aij, i≠jhas its eigenvalues in the union of the intervals [bij?yi, bij+ xi]. Moreover, given such a set of intervals, we derive better bounds for the eigenvalues of B using the 2n quantities {bii?y, bii+xi}, i=1,..., n. 相似文献
13.
In this paper we introduce the class of strongly decomposable discrete sets and give an efficient algorithm for reconstructing discrete sets of this class from four projections. It is also shown that every Q-convex set (along the set of directions {x, y}) consisting of several components is strongly decomposable. As a consequence of strong decomposability we get that in a subclass of hv-convex discrete sets the reconstruction from four projections can be solved in polynomial time. 相似文献
14.
Let X be a set. A collection of subsets of X has subinfinite rank if whenever ? , ∩≠ø, and is infinite, then there are two distinct elements of , one of which is a subset of the other. Theorem. AT1space with a base of subinfinite rank is hereditarily metacompact. 相似文献
15.
Let V be an n-dimensional vector space and T?Hom(V,V). The first result shows that if Cm(T), the mth compound of T, possesses a basis of eigenvectors, then it possesses a basis consisting of decomposable eigenvectors in the mth Grassman space over V. The paper also contains a simplified proof of a recent result of S. Belcerzyk on traces of compounds as well as conditions for the equality of fixed coefficients in the polynomials det(λA+μX) and det(λB+μX). 相似文献
16.
Let A,B be nonempty subsets of a Banach space X and let T:A→B be a non-self mapping. Under appropriate conditions, we study the existence of solutions for the minimization problem min x∈A ∥x?Tx∥. 相似文献
17.
18.
Houmem Belkhechine 《Discrete Mathematics》2017,340(12):2986-2994
Given a tournament , a module of is a subset of such that for and , if and only if . The trivial modules of are ,
and . The tournament is indecomposable if all its modules are trivial; otherwise it is decomposable. The decomposability index of , denoted by , is the smallest number of arcs of that must be reversed to make indecomposable. For , let be the maximum of over the tournaments with vertices. We prove that and that the lower bound is reached by the transitive tournaments. 相似文献
19.
We associate a graph G ?(P) to a partially ordered set (poset, briefly) with the least element?0, as an undirected graph with vertex set P ?=P?{0} and, for two distinct vertices x and y, x is adjacent to?y in?G ?(P) if and only if {x,y} ? ={0}, where, for a subset?S of?P, S ? is the set of all elements x∈P with x≦s for all s∈S. We study some basic properties of?G ?(P). Also, we completely investigate the planarity of?G ?(P). 相似文献
20.