共查询到20条相似文献,搜索用时 31 毫秒
1.
Hein van der Holst 《Linear algebra and its applications》2008,428(7):1587-1600
For a graph G=(V,E) with vertex-set V={1,2,…,n}, which is allowed to have parallel edges, and for a field F, let S(G;F) be the set of all F-valued symmetric n×n matrices A which represent G. The maximum corank of a graph G is the maximum possible corank over all A∈S(G;F). If (G1,G2) is a (?2)-separation, we give a formula which relates the maximum corank of G to the maximum corank of some small variations of G1 and G2. 相似文献
2.
Let Mn be the algebra of all n×n matrices, and let φ:Mn→Mn be a linear mapping. We say that φ is a multiplicative mapping at G if φ(ST)=φ(S)φ(T) for any S,T∈Mn with ST=G. Fix G∈Mn, we say that G is an all-multiplicative point if every multiplicative linear bijection φ at G with φ(In)=In is a multiplicative mapping in Mn, where In is the unit matrix in Mn. We mainly show in this paper the following two results: (1) If G∈Mn with detG=0, then G is an all-multiplicative point in Mn; (2) If φ is an multiplicative mapping at In, then there exists an invertible matrix P∈Mn such that either φ(S)=PSP-1 for any S∈Mn or φ(T)=PTtrP-1 for any T∈Mn. 相似文献
3.
Vladimir Nikiforov 《Linear algebra and its applications》2006,414(1):347-360
Let G be a graph with n vertices and m edges and let μ(G) = μ1(G) ? ? ? μn(G) be the eigenvalues of its adjacency matrix. Set s(G)=∑u∈V(G)∣d(u)-2m/n∣. We prove that
4.
A.R. Ashrafi M. SaheliM. Ghorbani 《Journal of Computational and Applied Mathematics》2011,235(16):4561-4566
Let G be a molecular graph. The eccentric connectivity index ξc(G) is defined as ξc(G)=∑u∈V(G)degG(u)εG(u), where degG(u) denotes the degree of vertex u and εG(u) is the largest distance between u and any other vertex v of G. In this paper exact formulas for the eccentric connectivity index of TUC4C8(S) nanotube and TC4C8(S) nanotorus are given. 相似文献
5.
Wayne Barrett 《Linear algebra and its applications》2011,434(10):2197-2203
Let G=(V,E) be a graph with V={1,2,…,n}. Denote by S(G) the set of all real symmetric n×n matrices A=[ai,j] with ai,j≠0, i≠j if and only if ij is an edge of G. Denote by I↗(G) the set of all pairs (p,q) of natural numbers such that there exists a matrix A∈S(G) with at most p positive and q negative eigenvalues. We show that if G is the join of G1 and G2, then I↗(G)?{(1,1)}=I↗(G1∨K1)∩I↗(G2∨K1)?{(1,1)}. Further, we show that if G is a graph with s isolated vertices, then , where denotes the graph obtained from G be removing all isolated vertices, and we give a combinatorial characterization of graphs G with (1,1)∈I↗(G). We use these results to determine I↗(G) for every complete multipartite graph G. 相似文献
6.
Let G be a graph with n vertices and ν(G) be the matching number of G. Let η(G) denote the nullity of G (the multiplicity of the eigenvalue zero of G). It is well known that if G is a tree, then η(G)=n-2ν(G). Tan and Liu [X. Tan, B. Liu, On the nullity of unicyclic graphs, Linear Alg. Appl. 408 (2005) 212-220] proved that the nullity set of all unicyclic graphs with n vertices is {0,1,…,n-4} and characterized the unicyclic graphs with η(G)=n-4. In this paper, we characterize the unicyclic graphs with η(G)=n-5, and we prove that if G is a unicyclic graph, then η(G) equals , or n-2ν(G)+2. We also give a characterization of these three types of graphs. Furthermore, we determine the unicyclic graphs G with η(G)=0, which answers affirmatively an open problem by Tan and Liu. 相似文献
7.
We consider the (Ihara) zeta functions of line graphs, middle graphs and total graphs of a regular graph and their (regular or irregular) covering graphs. Let L(G), M(G) and T(G) denote the line, middle and total graph of G, respectively. We show that the line, middle and total graph of a (regular and irregular, respectively) covering of a graph G is a (regular and irregular, respectively) covering of L(G), M(G) and T(G), respectively. For a regular graph G, we express the zeta functions of the line, middle and total graph of any (regular or irregular) covering of G in terms of the characteristic polynomial of the covering. Also, the complexities of the line, middle and total graph of any (regular or irregular) covering of G are computed. Furthermore, we discuss the L-functions of the line, middle and total graph of a regular graph G. 相似文献
8.
For a graph G of order n, the maximum nullity of G is defined to be the largest possible nullity over all real symmetric n×n matrices A whose (i,j)th entry (for i≠j) is nonzero whenever {i,j} is an edge in G and is zero otherwise. Maximum nullity and the related parameter minimum rank of the same set of matrices have been studied extensively. A new parameter, maximum generic nullity, is introduced. Maximum generic nullity provides insight into the structure of the null-space of a matrix realizing maximum nullity of a graph. It is shown that maximum generic nullity is bounded above by edge connectivity and below by vertex connectivity. Results on random graphs are used to show that as n goes to infinity almost all graphs have equal maximum generic nullity, vertex connectivity, edge connectivity, and minimum degree. 相似文献
9.
Ting-Chung Chang 《Linear algebra and its applications》2011,435(10):2451-2461
By the signless Laplacian of a (simple) graph G we mean the matrix Q(G)=D(G)+A(G), where A(G),D(G) denote respectively the adjacency matrix and the diagonal matrix of vertex degrees of G. For every pair of positive integers n,k, it is proved that if 3?k?n-3, then Hn,k, the graph obtained from the star K1,n-1 by joining a vertex of degree 1 to k+1 other vertices of degree 1, is the unique connected graph that maximizes the largest signless Laplacian eigenvalue over all connected graphs with n vertices and n+k edges. 相似文献
10.
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. 相似文献
11.
Henry Escuadro 《Discrete Mathematics》2008,308(10):1951-1961
Let G be a connected graph of order 3 or more and let be a coloring of the edges of G (where adjacent edges may be colored the same). For each vertex v of G, the color code of v is the k-tuple c(v)=(a1,a2,…,ak), where ai is the number of edges incident with v that are colored i (1?i?k). The coloring c is called detectable if distinct vertices have distinct color codes; while the detection number det(G) of G is the minimum positive integer k for which G has a detectable k-coloring. For each integer n?3, let DT(n) be the maximum detection number among all trees of order n and dT(n) the minimum detection number among all trees of order n. The numbers DT(n) and dT(n) are determined for all integers n?3. Furthermore, it is shown that for integers k?2 and n?3, there exists a tree T of order n having det(T)=k if and only if dT(n)?k?DT(n). 相似文献
12.
Mario Valencia-Pabon 《Discrete Mathematics》2006,306(18):2275-2281
Let α(G) and χ(G) denote the independence number and chromatic number of a graph G, respectively. Let G×H be the direct product graph of graphs G and H. We show that if G and H are circular graphs, Kneser graphs, or powers of cycles, then α(G×H)=max{α(G)|V(H)|,α(H)|V(G)|} and χ(G×H)=min{χ(G),χ(H)}. 相似文献
13.
Let G=(V,E) be a connected graph. For a symmetric, integer-valued function δ on V×V, where K is an integer constant, N0 is the set of nonnegative integers, and Z is the set of integers, we define a C-mapping by F(u,v,m)=δ(u,v)+m−K. A coloring c of G is an F-coloring if F(u,v,|c(u)−c(v)|)?0 for every two distinct vertices u and v of G. The maximum color assigned by c to a vertex of G is the value of c, and the F-chromatic number F(G) is the minimum value among all F-colorings of G. For an ordering of the vertices of G, a greedy F-coloring c of s is defined by (1) c(v1)=1 and (2) for each i with 1?i<n, c(vi+1) is the smallest positive integer p such that F(vj,vi+1,|c(vj)−p|)?0, for each j with 1?j?i. The greedy F-chromatic number gF(s) of s is the maximum color assigned by c to a vertex of G. The greedy F-chromatic number of G is gF(G)=min{gF(s)} over all orderings s of V. The Grundy F-chromatic number is GF(G)=max{gF(s)} over all orderings s of V. It is shown that gF(G)=F(G) for every graph G and every F-coloring defined on G. The parameters gF(G) and GF(G) are studied and compared for a special case of the C-mapping F on a connected graph G, where δ(u,v) is the distance between u and v and . 相似文献
14.
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. 相似文献
15.
Oscar Rojo 《Linear algebra and its applications》2008,428(4):754-764
Let G=(V(G),E(G)) be a unicyclic simple undirected graph with largest vertex degree Δ. Let Cr be the unique cycle of G. The graph G-E(Cr) is a forest of r rooted trees T1,T2,…,Tr with root vertices v1,v2,…,vr, respectively. Let
16.
Alan B. Poritz 《Linear algebra and its applications》2011,434(6):1425-4165
When an n×n doubly stochastic matrix A acts on Rn on the left as a linear transformation and P is an n-long probability vector, we refer to the new probability vector AP as the stochastic average of the pair (A,P). Let Γn denote the set of pairs (A,P) whose stochastic average preserves the entropy of P:H(AP)=H(P). Γn is a subset of Bn×Σn where Bn is the Birkhoff polytope and Σn is the probability simplex.We characterize Γn and determine its geometry, topology,and combinatorial structure. For example, we find that (A,P)∈Γn if and only if AtAP=P. We show that for any n, Γn is a connected set, and is in fact piecewise-linearly contractible in Bn×Σn. We write Γn as a finite union of product subspaces, in two distinct ways. We derive the geometry of the fibers (A,·) and (·,P) of Γn. Γ3 is worked out in detail. Our analysis exploits the convexity of xlogx and the structure of an efficiently computable bipartite graph that we associate to each ds-matrix. This graph also lets us represent such a matrix in a permutation-equivalent, block diagonal form where each block is doubly stochastic and fully indecomposable. 相似文献
17.
A Steiner tree for a set S of vertices in a connected graph G is a connected subgraph of G with a smallest number of edges that contains S. The Steiner interval I(S) of S is the union of all the vertices of G that belong to some Steiner tree for S. If S={u,v}, then I(S)=I[u,v] is called the interval between u and v and consists of all vertices that lie on some shortest u-v path in G. The smallest cardinality of a set S of vertices such that ?u,v∈SI[u,v]=V(G) is called the geodetic number and is denoted by g(G). The smallest cardinality of a set S of vertices of G such that I(S)=V(G) is called the Steiner geodetic number of G and is denoted by sg(G). We show that for distance-hereditary graphs g(G)?sg(G) but that g(G)/sg(G) can be arbitrarily large if G is not distance hereditary. An efficient algorithm for finding the Steiner interval for a set of vertices in a distance-hereditary graph is described and it is shown how contour vertices can be used in developing an efficient algorithm for finding the Steiner geodetic number of a distance-hereditary graph. 相似文献
18.
Linda Eroh 《Discrete Mathematics》2008,308(18):4212-4220
Let G be a connected graph and S⊆V(G). Then the Steiner distance of S, denoted by dG(S), is the smallest number of edges in a connected subgraph of G containing S. Such a subgraph is necessarily a tree called a Steiner tree for S. The Steiner interval for a set S of vertices in a graph, denoted by I(S) is the union of all vertices that belong to some Steiner tree for S. If S={u,v}, then I(S) is the interval I[u,v] between u and v. A connected graph G is 3-Steiner distance hereditary (3-SDH) if, for every connected induced subgraph H of order at least 3 and every set S of three vertices of H, dH(S)=dG(S). The eccentricity of a vertex v in a connected graph G is defined as e(v)=max{d(v,x)|x∈V(G)}. A vertex v in a graph G is a contour vertex if for every vertex u adjacent with v, e(u)?e(v). The closure of a set S of vertices, denoted by I[S], is defined to be the union of intervals between pairs of vertices of S taken over all pairs of vertices in S. A set of vertices of a graph G is a geodetic set if its closure is the vertex set of G. The smallest cardinality of a geodetic set of G is called the geodetic number of G and is denoted by g(G). A set S of vertices of a connected graph G is a Steiner geodetic set for G if I(S)=V(G). The smallest cardinality of a Steiner geodetic set of G is called the Steiner geodetic number of G and is denoted by sg(G). We show that the contour vertices of 3-SDH and HHD-free graphs are geodetic sets. For 3-SDH graphs we also show that g(G)?sg(G). An efficient algorithm for finding Steiner intervals in 3-SDH graphs is developed. 相似文献
19.
Clément de Seguins Pazzis 《Linear algebra and its applications》2011,435(11):2708-2721
Let (K) be a field. Given an arbitrary linear subspace V of Mn(K) of codimension less than n-1, a classical result states that V generates the (K)-algebra Mn(K). Here, we strengthen this statement in three ways: we show that Mn(K) is spanned by the products of the form AB with (A,B)∈V2; we prove that every matrix in Mn(K) can be decomposed into a product of matrices of V; finally, when V is a linear perplane of Mn(K) and n>2, we show that every matrix in Mn(K) is a product of two elements of V. 相似文献
20.
The matrix A = (aij) ∈ Sn is said to lie on a strict undirected graph G if aij = 0 (i ≠ j) whenever (i, j) is not in E(G). If S is skew-symmetric, the isospectral flow maintains the spectrum of A. We consider isospectral flows that maintain a matrix A(t) on a given graph G. We review known results for a graph G that is a (generalised) path, and construct isospectral flows for a (generalised) ring, and a star, and show how a flow may be constructed for a general graph. The analysis may be applied to the isospectral problem for a lumped-mass finite element model of an undamped vibrating system. In that context, it is important that the flow maintain other properties such as irreducibility or positivity, and we discuss whether they are maintained. 相似文献