共查询到20条相似文献,搜索用时 46 毫秒
1.
John Sinkovic 《Linear algebra and its applications》2010,432(8):2052-411
Let G=(V,E) be a graph with V={1,2,…,n}. Define S(G) as the set of all n×n real-valued symmetric matrices A=[aij] with aij≠0,i≠j if and only if ij∈E. By M(G) we denote the largest possible nullity of any matrix A∈S(G). The path cover number of a graph G, denoted P(G), is the minimum number of vertex disjoint paths occurring as induced subgraphs of G which cover all the vertices of G.There has been some success with relating the path cover number of a graph to its maximum nullity. Johnson and Duarte [5], have shown that for a tree T,M(T)=P(T). Barioli et al. [2], show that for a unicyclic graph G,M(G)=P(G) or M(G)=P(G)-1. Notice that both families of graphs are outerplanar. We show that for any outerplanar graph G,M(G)?P(G). Further we show that for any partial 2-path G,M(G)=P(G). 相似文献
2.
Daniel M. Kane 《Journal of Number Theory》2006,120(1):92-100
Let B∈Z[x] be a polynomial with b=B(0). Let S be a complete residue class modulo b containing 0. We attempt to classify the polynomials B and residue classes S so that for every polynomial P∈Z[x] there exists a polynomial Q with coefficients in S such that . 相似文献
3.
Yanfeng Luo 《Discrete Mathematics》2009,309(20):5943-1987
Let G be a finite group and A a nonempty subset (possibly containing the identity element) of G. The Bi-Cayley graph X=BC(G,A) of G with respect to A is defined as the bipartite graph with vertex set G×{0,1} and edge set {{(g,0),(sg,1)}∣g∈G,s∈A}. A graph Γ admitting a perfect matching is called n-extendable if ∣V(Γ)∣≥2n+2 and every matching of size n in Γ can be extended to a perfect matching of Γ. In this paper, the extendability of Bi-Cayley graphs of finite abelian groups is explored. In particular, 2-extendable and 3-extendable Bi-Cayley graphs of finite abelian groups are characterized. 相似文献
4.
Shih Ping Tung 《Journal of Number Theory》2010,130(4):912-929
In this paper we study the maximum-minimum value of polynomials over the integer ring Z. In particular, we prove the following: Let F(x,y) be a polynomial over Z. Then, maxx∈Z(T)miny∈Z|F(x,y)|=o(T1/2) as T→∞ if and only if there is a positive integer B such that maxx∈Zminy∈Z|F(x,y)|?B. We then apply these results to exponential diophantine equations and obtain that: Let f(x,y), g(x,y) and G(x,y) be polynomials over Q, G(x,y)∈(Q[x,y]−Q[x])∪Q, and b a positive integer. For every α in Z, there is a y in Z such that f(α,y)+g(α,y)bG(α,y)=0 if and only if for every integer α there exists an h(x)∈Q[x] such that f(x,h(x))+g(x,h(x))bG(x,h(x))≡0, and h(α)∈Z. 相似文献
5.
Susana Furtado 《Linear algebra and its applications》2008,429(7):1663-1678
Let F be a field. In [Djokovic, Product of two involutions, Arch. Math. 18 (1967) 582-584] it was proved that a matrix A∈Fn×n can be written as A=BC, for some involutions B,C∈Fn×n, if and only if A is similar to A-1. In this paper we describe the possible eigenvalues of the matrices B and C.As a consequence, in case charF≠2, we describe the possible similarity classes of (P11⊕P22)P-1, when the nonsingular matrix P=[Pij]∈Fn×n, i,j∈{1,2} and P11∈Fs×s, varies.When F is an algebraically closed field and charF≠2, we also describe the possible similarity classes of [Aij]∈Fn×n, i,j∈{1,2}, when A11 and A22 are square zero matrices and A12 and A21 vary. 相似文献
6.
Florin Nicolae 《Journal of Number Theory》2007,124(1):26-30
Let K/Q be a finite Galois extension with the Galois group G, let χ1,…,χr be the irreducible non-trivial characters of G, and let A be the C-algebra generated by the Artin L-functions L(s,χ1),…,L(s,χr). Let B be the subalgebra of A generated by the L-functions corresponding to induced characters of non-trivial one-dimensional characters of subgroups of G. We prove: (1) B is of Krull dimension r and has the same quotient field as A; (2) B=A iff G is M-group; (3) the integral closure of B in A equals A iff G is quasi-M-group. 相似文献
7.
Let Mm,n(B) be the semimodule of all m×n Boolean matrices where B is the Boolean algebra with two elements. Let k be a positive integer such that 2?k?min(m,n). Let B(m,n,k) denote the subsemimodule of Mm,n(B) spanned by the set of all rank k matrices. We show that if T is a bijective linear mapping on B(m,n,k), then there exist permutation matrices P and Q such that T(A)=PAQ for all A∈B(m,n,k) or m=n and T(A)=PAtQ for all A∈B(m,n,k). This result follows from a more general theorem we prove concerning the structure of linear mappings on B(m,n,k) that preserve both the weight of each matrix and rank one matrices of weight k2. Here the weight of a Boolean matrix is the number of its nonzero entries. 相似文献
8.
Komjáth in 1984 proved that, for each sequence (An) of analytic subsets of a Polish space X, if lim supn∈HAn is uncountable for every H∈ω[N] then ?n∈GAn is uncountable for some G∈ω[N]. This fact, by our definition, means that the σ-ideal [X]?ω has property (LK). We prove that every σ-ideal generated by X/E has property (LK), for an equivalence relation E⊂X2 of type Fσ with uncountably many equivalence classes. We also show the parametric version of this result. Finally, the invariance of property (LK) with respect to various operations is studied. 相似文献
9.
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. 相似文献
10.
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. 相似文献
11.
Let G be a graph. If u,v∈V(G), a u-vshortest path of G is a path linking u and v with minimum number of edges. The closed interval I[u,v] consists of all vertices lying in some u-v shortest path of G. For S⊆V(G), the set I[S] is the union of all sets I[u,v] for u,v∈S. We say that S is a convex set if I[S]=S. The convex hull of S, denoted Ih[S], is the smallest convex set containing S. A set S is a hull set of G if Ih[S]=V(G). The cardinality of a minimum hull set of G is the hull number of G, denoted by hn(G). In this work we prove that deciding whether hn(G)≤k is NP-complete.We also present polynomial-time algorithms for computing hn(G) when G is a unit interval graph, a cograph or a split graph. 相似文献
12.
Maria Adam 《Applied mathematics and computation》2011,217(9):4699-4709
For an n × n normal matrix A, whose numerical range NR[A] is a k-polygon (k ? n), an n × (k − 1) isometry matrix P is constructed by a unit vector υ∈Cn, and NR[P∗AP] is inscribed to NR[A]. In this paper, using the notations of NR[P∗AP] and some properties from projective geometry, an n × n diagonal matrix B and an n × (k − 2) isometry matrix Q are proposed such that NR[P∗AP] and NR[Q∗BQ] have as common support lines the edges of the k-polygon and share the same boundary points with the polygon. It is proved that the boundary of NR[P∗AP] is a differentiable curve and the boundary of the numerical range of a 3 × 3 matrix P∗AP is an ellipse, when the polygon is a quadrilateral. 相似文献
13.
In this paper, we introduce a total step method for solving a system of linear complementarity problems with perturbations and interval data. It is applied to two interval matrices [A] and [B] and two interval vectors [b] and [c]. We prove that the sequence generated by the total step method converges to ([x∗],[y∗]) which includes the solution set for the system of linear complementarity problems defined by any fixed A∈[A],B∈[B],b∈[b] and c∈[c]. We also consider a modification of the method and show that, if we start with two interval vectors containing the limits, then the iterates contain the limits. We close our paper with two examples which illustrate our theoretical results. 相似文献
14.
A. Ballester-Bolinches John Cossey R. Esteban-Romero 《Annali di Matematica Pura ed Applicata》2010,189(4):567-570
For a finite group G we define the graph Γ(G) to be the graph whose vertices are the conjugacy classes of cyclic subgroups of G and two conjugacy classes ${\mathcal {A}, \mathcal {B}}For a finite group G we define the graph Γ(G) to be the graph whose vertices are the conjugacy classes of cyclic subgroups of G and two conjugacy classes A, B{\mathcal {A}, \mathcal {B}} are joined by an edge if for some A ? A, B ? B A{A \in \mathcal {A},\, B \in \mathcal {B}\, A} and B permute. We characterise those groups G for which Γ(G) is complete. 相似文献
15.
A strong defensive alliance in a graph G=(V,E) is a set of vertices A⊆V, for which every vertex v∈A has at least as many neighbors in A as in V−A. We call a partition A,B of vertices to be an alliance-free partition, if neither A nor B contains a strong defensive alliance as a subset. We prove that a connected graph G has an alliance-free partition exactly when G has a block that is other than an odd clique or an odd cycle. 相似文献
16.
Let G be a finite and simple graph with vertex set V(G), and let f:V(G)→{−1,1} be a two-valued function. If ∑x∈N[v]f(x)≥1 for each v∈V(G), where N[v] is the closed neighborhood of v, then f is a signed dominating function on G. A set {f1,f2,…,fd} of signed dominating functions on G with the property that for each x∈V(G), is called a signed dominating family (of functions) on G. The maximum number of functions in a signed dominating family on G is the signed domatic number on G. In this paper, we investigate the signed domatic number of some circulant graphs and of the torus Cp×Cq. 相似文献
17.
Li-Ping Huang 《Linear algebra and its applications》2010,433(1):221-232
Denote by G=(V,∼) a graph which V is the vertex set and ∼ is an adjacency relation on a subset of V×V. In this paper, the good distance graph is defined. Let (V,∼) and (V′,∼′) be two good distance graphs, and φ:V→V′ be a map. The following theorem is proved: φ is a graph isomorphism ⇔φ is a bounded distance preserving surjective map in both directions ⇔φ is a distance k preserving surjective map in both directions (where k<diam(G)/2 is a positive integer), etc. Let D be a division ring with an involution such that both |F∩ZD|?3 and D is not a field of characteristic 2 with D=F, where and ZD is the center of D. Let Hn(n?2) be the set of n×n Hermitian matrices over D. It is proved that (Hn,∼) is a good distance graph, where A∼B⇔rank(A-B)=1 for all A,B∈Hn. 相似文献
18.
Let K be a complete ultrametric algebraically closed field of characteristic π. Let P,Q be in K[x] with P′Q′ not identically 0. Consider two different functions f,g analytic or meromorphic inside a disk |x−a|<r (resp. in all K), satisfying P(f)=Q(g). By applying the Nevanlinna's values distribution Theory in characteristic π, we give sufficient conditions on the zeros of P′,Q′ to assure that both f,g are “bounded” in the disk (resp. are constant). If π≠2 and deg(P)=4, we examine the particular case when Q=λP (λ∈K) and we derive several sets of conditions characterizing the existence of two distinct functions f,g meromorphic in K such that P(f)=λP(g). 相似文献
19.
Gyula Károlyi 《Journal of Combinatorial Theory, Series A》2009,116(3):741-746
Let A≠B be nonempty subsets of the group of integers modulo a prime p. If p?|A|+|B|−2, then at least |A|+|B|−2 different residue classes can be represented as a+b, where a∈A, b∈B and a≠b. This result complements the solution of a problem of Erd?s and Heilbronn obtained by Alon, Nathanson, and Ruzsa. 相似文献
20.
Let G=(V,E) be a graph. A set S⊆V is a defensive alliance if |N[x]∩S|?|N[x]-S| for every x∈S. Thus, each vertex of a defensive alliance can, with the aid of its neighbors in S, be defended from attack by its neighbors outside of S. An entire set S is secure if any subset X⊆S, not just singletons, can be defended from an attack from outside of S, under an appropriate definition of what such a defense implies. The security number s(G) of G is the cardinality of a smallest secure set. Bounds on s(G) are presented. 相似文献