共查询到20条相似文献,搜索用时 609 毫秒
1.
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. 相似文献
2.
Equitable colorings of Kronecker products of graphs 总被引:1,自引:0,他引:1
Wu-Hsiung Lin 《Discrete Applied Mathematics》2010,158(16):1816-1826
For a positive integer k, a graph G is equitably k-colorable if there is a mapping f:V(G)→{1,2,…,k} such that f(x)≠f(y) whenever xy∈E(G) and ||f−1(i)|−|f−1(j)||≤1 for 1≤i<j≤k. The equitable chromatic number of a graph G, denoted by χ=(G), is the minimum k such that G is equitably k-colorable. The equitable chromatic threshold of a graph G, denoted by , is the minimum t such that G is equitably k-colorable for k≥t. The current paper studies equitable chromatic numbers of Kronecker products of graphs. In particular, we give exact values or upper bounds on χ=(G×H) and when G and H are complete graphs, bipartite graphs, paths or cycles. 相似文献
3.
4.
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 . 相似文献
5.
Alewyn P. Burger 《Discrete Mathematics》2009,309(8):2473-2036
The relationship ρL(G)≤ρ(G)≤γ(G) between the lower packing number ρL(G), the packing number ρ(G) and the domination number γ(G) of a graph G is well known. In this paper we establish best possible bounds on the ratios of the packing numbers of any (connected) graph to its six domination-related parameters (the lower and upper irredundance numbers ir and IR, the lower and upper independence numbers i and β, and the lower and upper domination numbers γ and Γ). In particular, best possible constants aθ, bθ, cθ and dθ are found for which the inequalities and hold for any connected graph G and all θ∈{ir,γ,i,β,Γ,IR}. From our work it follows, for example, that and for any connected graph G, and that these inequalities are best possible. 相似文献
6.
Roberto Beneduci 《Linear algebra and its applications》2010,433(6):1224-1239
Our starting point is the proof of the following property of a particular class of matrices. Let T={Ti,j} be a n×m non-negative matrix such that ∑jTi,j=1 for each i. Suppose that for every pair of indices (i,j), there exists an index l such that Ti,l≠Tj,l. Then, there exists a real vector k=(k1,k2,…,km)T,ki≠kj,i≠j;0<ki?1, such that, if i≠j.Then, we apply that property of matrices to probability theory. Let us consider an infinite sequence of linear functionals , corresponding to an infinite sequence of probability measures {μ(·)(i)}i∈N, on the Borel σ-algebra such that, . The property of matrices described above allows us to construct a real bounded one-to-one piecewise continuous and continuous from the left function f such that
7.
Songqiao Wen 《Journal of multivariate analysis》2007,98(4):743-756
Let X1,X2,…,Xn be independent exponential random variables such that Xi has failure rate λ for i=1,…,p and Xj has failure rate λ* for j=p+1,…,n, where p≥1 and q=n-p≥1. Denote by Di:n(p,q)=Xi:n-Xi-1:n the ith spacing of the order statistics , where X0:n≡0. It is shown that Di:n(p,q)?lrDi+1:n(p,q) for i=1,…,n-1, and that if λ?λ* then , and for i=1,…,n, where ?lr denotes the likelihood ratio order. The main results are used to establish the dispersive orderings between spacings. 相似文献
8.
Mirko Lepovi? 《Discrete Mathematics》2007,307(6):730-738
Let G be a simple graph of order n. Let and , where a and b are two nonzero integers and m is a positive integer such that m is not a perfect square. We say that Ac=[cij] is the conjugate adjacency matrix of the graph G if cij=c for any two adjacent vertices i and j, for any two nonadjacent vertices i and j, and cij=0 if i=j. Let PG(λ)=|λI-A| and denote the characteristic polynomial and the conjugate characteristic polynomial of G, respectively. In this work we show that if then , where denotes the complement of G. In particular, we prove that if and only if PG(λ)=PH(λ) and . Further, let Pc(G) be the collection of conjugate characteristic polynomials of vertex-deleted subgraphs Gi=G?i(i=1,2,…,n). If Pc(G)=Pc(H) we prove that , provided that the order of G is greater than 2. 相似文献
9.
Françoise Lust-Piquard 《Advances in Mathematics》2004,185(2):289-327
Let G be a lca group with a fixed g0∈G, spanning an infinite subgroup. Let τj, acting on L2(Gn), be translation by go in the jth coordinate; the discrete derivatives ∂j=I−τj define a discrete Laplacian and discrete Riesz transforms . We get dimension-free estimates
10.
Let G=(V,E) be a simple graph with vertex degrees d1,d2,…,dn. The Randi? index R(G) is equal to the sum over all edges (i,j)∈E of weights . We prove several conjectures, obtained by the system AutoGraphiX, relating R(G) and the chromatic number χ(G). The main result is χ(G)≤2R(G). To prove it, we also show that if v∈V is a vertex of minimum degree δ of G, G−v the graph obtained from G by deleting v and all incident edges, and Δ the maximum degree of G, then . 相似文献
11.
For a simple graph G, let denote the complement of G relative to the complete graph and let PG(x)=det(xI-A(G)) where A(G) denotes the adjacency matrix of G. The complete product G∇H of two simple graphs G and H is the graph obtained from G and H by joining every vertex of G to every vertex of H. In [2]PG∇H(x) is represented in terms of PG, , PH and . In this paper we extend the notion of complete product of simple graphs to that of generalized complete product of matrices and obtain their characteristic polynomials. 相似文献
12.
Gregory Lupton 《Topology and its Applications》2007,154(6):1107-1118
Let be a fibration of simply connected CW complexes of finite type with classifying map . We study the evaluation subgroup Gn(E,X;j) of the fibre inclusion as an invariant of the fibre-homotopy type of ξ. For spherical fibrations, we show the evaluation subgroup may be expressed as an extension of the Gottlieb group of the fibre sphere provided the classifying map h induces the trivial map on homotopy groups. We extend this result after rationalization: We show that the decomposition G∗(E,X;j)⊗Q=(G∗(X)⊗Q)⊕(π∗(B)⊗Q) is equivalent to the condition Q(h?)=0. 相似文献
13.
Thomas Böhme 《Discrete Mathematics》2006,306(7):666-669
We prove that for every graph H with the minimum degree δ?5, the third iterated line graph L3(H) of H contains as a minor. Using this fact we prove that if G is a connected graph distinct from a path, then there is a number kG such that for every i?kG the i-iterated line graph of G is -linked. Since the degree of Li(G) is even, the result is best possible. 相似文献
14.
Acyclic edge colouring of planar graphs without short cycles 总被引:1,自引:0,他引:1
Mieczys?aw Borowiecki 《Discrete Mathematics》2010,310(9):1445-2495
Let G=(V,E) be any finite graph. A mapping C:E→[k] is called an acyclic edgek-colouring of G, if any two adjacent edges have different colours and there are no bichromatic cycles in G. In other words, for every pair of distinct colours i and j, the subgraph induced in G by all the edges which have colour i or j, is acyclic. The smallest number k of colours, such that G has an acyclic edge k-colouring is called the acyclic chromatic index of G, denoted by .In 2001, Alon et al. conjectured that for any graph G it holds that ; here Δ(G) stands for the maximum degree of G.In this paper we prove this conjecture for planar graphs with girth at least 5 and for planar graphs not containing cycles of length 4,6,8 and 9. We also show that if G is planar with girth at least 6. Moreover, we find an upper bound for the acyclic chromatic index of planar graphs without cycles of length 4. Namely, we prove that if G is such a graph, then . 相似文献
15.
Sarah Crown 《Journal of Combinatorial Theory, Series A》2009,116(3):595-612
Let G be a simple graph on n vertices, and let χG(λ) denote the chromatic polynomial of G. In this paper, we define the cyclic coloring complex, Δ(G), and determine the dimensions of its homology groups for simple graphs. In particular, we show that if G has r connected components, the dimension of (n−3)rd homology group of Δ(G) is equal to (n−(r+1)) plus , where is the rth derivative of χG(λ). We also define a complex ΔC(G), whose r-faces consist of all ordered set partitions [B1,…,Br+2] where none of the Bi contain an edge of G and where 1∈B1. We compute the dimensions of the homology groups of this complex, and as a result, obtain the dimensions of the multilinear parts of the cyclic homology groups of C[x1,…,xn]/{xixj|ij is an edge of G}. We show that when G is a connected graph, the homology of ΔC(G) has nonzero homology only in dimension n−2, and the dimension of this homology group is . In this case, we provide a bijection between a set of homology representatives of ΔC(G) and the acyclic orientations of G with a unique source at v, a vertex of G. 相似文献
16.
Mordecai J. Golin 《Discrete Mathematics》2010,310(4):792-803
Let T(G) be the number of spanning trees in graph G. In this note, we explore the asymptotics of T(G) when G is a circulant graph with given jumps.The circulant graph is the 2k-regular graph with n vertices labeled 0,1,2,…,n−1, where node i has the 2k neighbors i±s1,i±s2,…,i±sk where all the operations are . We give a closed formula for the asymptotic limit as a function of s1,s2,…,sk. We then extend this by permitting some of the jumps to be linear functions of n, i.e., letting si, di and ei be arbitrary integers, and examining
17.
The pebbling number of a graph G, f(G), is the least n such that, no matter how n pebbles are placed on the vertices of G, we can move a pebble to any vertex by a sequence of pebbling moves, each move taking two pebbles off one vertex and placing one on an adjacent vertex. Let p1,p2,…,pn be positive integers and G be such a graph, V(G)=n. The thorn graph of the graph G, with parameters p1,p2,…,pn, is obtained by attaching pi new vertices of degree 1 to the vertex ui of the graph G, i=1,2,…,n. Graham conjectured that for any connected graphs G and H, f(G×H)≤f(G)f(H). We show that Graham’s conjecture holds true for a thorn graph of the complete graph with every by a graph with the two-pebbling property. As a corollary, Graham’s conjecture holds when G and H are the thorn graphs of the complete graphs with every . 相似文献
18.
19.
Let G be a graph. The connectivity of G, κ(G), is the maximum integer k such that there exists a k-container between any two different vertices. A k-container of G between u and v, Ck(u,v), is a set of k-internally-disjoint paths between u and v. A spanning container is a container that spans V(G). A graph G is k∗-connected if there exists a spanning k-container between any two different vertices. The spanning connectivity of G, κ∗(G), is the maximum integer k such that G is w∗-connected for 1≤w≤k if G is 1∗-connected.Let x be a vertex in G and let U={y1,y2,…,yk} be a subset of V(G) where x is not in U. A spanningk−(x,U)-fan, Fk(x,U), is a set of internally-disjoint paths {P1,P2,…,Pk} such that Pi is a path connecting x to yi for 1≤i≤k and . A graph G is k∗-fan-connected (or -connected) if there exists a spanning Fk(x,U)-fan for every choice of x and U with |U|=k and x∉U. The spanning fan-connectivity of a graph G, , is defined as the largest integer k such that G is -connected for 1≤w≤k if G is -connected.In this paper, some relationship between κ(G), κ∗(G), and are discussed. Moreover, some sufficient conditions for a graph to be -connected are presented. Furthermore, we introduce the concept of a spanning pipeline-connectivity and discuss some sufficient conditions for a graph to be k∗-pipeline-connected. 相似文献
20.
Daqing Yang 《Discrete Mathematics》2009,309(13):4614-4623
Let be a directed graph. A transitive fraternal augmentation of is a directed graph with the same vertex set, including all the arcs of and such that for any vertices x,y,z,
- 1.
- if and then or (fraternity);
- 2.
- if and then (transitivity).