首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 929 毫秒
1.
For a graph G with the vertex set V(G), we denote by d(u,v) the distance between vertices u and v in G, by d(u) the degree of vertex u. The Hosoya polynomial of G is H(G)=∑{u,v}⊆V(G)xd(u,v). The partial Hosoya polynomials of G are for positive integer numbers m and n. It is shown that H(G1)−H(G2)=x2(x+1)2(H33(G1)−H33(G2)),H22(G1)−H22(G2)=(x2+x−1)2(H33(G1)−H33(G2)) and H23(G1)−H23(G2)=2(x2+x−1)(H33(G1)−H33(G2)) for arbitrary catacondensed benzenoid graphs G1 and G2 with equal number of hexagons. As an application, we give an affine relationship between H(G) with two other distance-based polynomials constructed by Gutman [I. Gutman, Some relations between distance-based polynomials of trees, Bulletin de l’Académie Serbe des Sciences et des Arts (Cl. Math. Natur.) 131 (2005) 1-7].  相似文献   

2.
Rank-width is a graph width parameter introduced by Oum and Seymour. It is known that a class of graphs has bounded rank-width if, and only if, it has bounded clique-width, and that the rank-width of G is less than or equal to its branch-width.The n×nsquare grid, denoted by Gn,n, is a graph on the vertex set {1,2,…,n}×{1,2,…,n}, where a vertex (x,y) is connected by an edge to a vertex (x,y) if and only if |xx|+|yy|=1.We prove that the rank-width of Gn,n is equal to n−1, thus solving an open problem of Oum.  相似文献   

3.
The strong chromatic index of a class of graphs   总被引:1,自引:0,他引:1  
The strong chromatic index of a graph G is the minimum integer k such that the edge set of G can be partitioned into k induced matchings. Faudree et al. [R.J. Faudree, R.H. Schelp, A. Gyárfás, Zs. Tuza, The strong chromatic index of graphs, Ars Combin. 29B (1990) 205-211] proposed an open problem: If G is bipartite and if for each edge xyE(G), d(x)+d(y)≤5, then sχ(G)≤6. Let H0 be the graph obtained from a 5-cycle by adding a new vertex and joining it to two nonadjacent vertices of the 5-cycle. In this paper, we show that if G (not necessarily bipartite) is not isomorphic to H0 and d(x)+d(y)≤5 for any edge xy of G then sχ(G)≤6. The proof of the result implies a linear time algorithm to produce a strong edge coloring using at most 6 colors for such graphs.  相似文献   

4.
The pair length of a graph G is the maximum positive integer k, such that the vertex set of G can be partitioned into disjoint pairs {x,x}, such that d(x,x)?k for every xV(G) and xy is an edge of G whenever xy is an edge. Chen asked whether the pair length of the cartesian product of two graphs is equal to the sum of their pair lengths. Our aim in this short note is to prove this result.  相似文献   

5.
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 GH 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]PGH(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.  相似文献   

6.
Let H be a simple graph with n vertices and G be a sequence of n rooted graphs G1,G2,…,Gn. Godsil and McKay [C.D. Godsil, B.D. McKay, A new graph product and its spectrum, Bull. Austral. Math. Soc. 18 (1978) 21-28] defined the rooted product H(G), of H by G by identifying the root vertex of Gi with the ith vertex of H, and determined the characteristic polynomial of H(G). In this paper we prove a general result on the determinants of some special matrices and, as a corollary, determine the characteristic polynomials of adjacency and Laplacian matrices of H(G).Rojo and Soto [O. Rojo, R. Soto, The spectra of the adjacency matrix and Laplacian matrix for some balanced trees, Linear Algebra Appl. 403 (2005) 97-117] computed the characteristic polynomials and the spectrum of adjacency and Laplacian matrices of a class of balanced trees. As an application of our results, we obtain their conclusions by a simple method.  相似文献   

7.
C. Balbuena 《Discrete Mathematics》2008,308(10):1985-1993
A matched sum graph G of two graphs G1 and G2 of the same order is obtained from the union of G1 and G2 and from joining each vertex of G1 with one vertex of G2 according to one bijection f between the vertices in V(G1) and V(G2). When G1=G2=H then f is just a permutation of V(H) and the corresponding matched sum graph is a permutation graph Hf. In this paper, we derive lower bounds for the connectivity, edge-connectivity, and different conditional connectivities in matched sum graphs, and present sufficient conditions which guarantee maximum values for these conditional connectivities.  相似文献   

8.
A tree is called starlike if it has exactly one vertex of degree greater than two. In [4] it was proved that two starlike treesG andH are cospectral if and only if they are isomorphic. We prove here that there exist no two non-isomorphic Laplacian cospectral starlike trees. Further, letG be a simple graph of ordern with vertex setV(G)={1,2, …,n} and letH={H 1,H 2, ...H n } be a family of rooted graphs. According to [2], the rooted productG(H) is the graph obtained by identifying the root ofH i with thei-th vertex ofG. In particular, ifH is the family of the paths $P_{k_1 } , P_{k_2 } , ..., P_{k_n } $ with the rooted vertices of degree one, in this paper the corresponding graphG(H) is called the sunlike graph and is denoted byG(k 1,k 2, …,k n ). For any (x 1,x 2, …,x n ) ∈I * n , whereI *={0,1}, letG(x 1,x 2, …,x n ) be the subgraph ofG which is obtained by deleting the verticesi 1, i2, …,i j ∈ V(G) (0≤j≤n), provided that $x_{i_1 } = x_{i_2 } = ... = x_{i_j } = 0$ . LetG(x 1,x 2,…, x n] be the characteristic polynomial ofG(x 1,x 2,…, x n ), understanding thatG[0, 0, …, 0] ≡ 1. We prove that $$G[k_1 , k_2 ,..., k_n ] = \Sigma _{x \in ^{I_ * ^n } } \left[ {\Pi _{i = 1}^n P_{k_i + x_i - 2} (\lambda )} \right]( - 1)^{n - (\mathop \Sigma \limits_{i = 1}^n x_i )} G[x_1 , x_2 , ..., x_n ]$$ where x=(x 1,x 2,…,x n );G[k 1,k 2,…,k n ] andP n (γ) denote the characteristic polynomial ofG(k 1,k 2,…,k n ) andP n , respectively. Besides, ifG is a graph with λ1(G)≥1 we show that λ1(G)≤λ1(G(k 1,k 2, ...,k n )) < for all positive integersk 1,k 2,…,k n , where λ1 denotes the largest eigenvalue.  相似文献   

9.
Let P(x) = Σi=0naixi be a nonnegative integral polynomial. The polynomial P(x) is m-graphical, and a multi-graph G a realization of P(x), provided there exists a multi-graph G containing exactly P(1) points where ai of these points have degree i for 0≤in. For multigraphs G, H having polynomials P(x), Q(x) and number-theoretic partitions (degree sequences) π, ?, the usual product P(x)Q(x) is shown to be the polynomial of the Cartesian product G × H, thus inducing a natural product π? which extends that of juxtaposing integral multiple copies of ?. Skeletal results are given on synthesizing a multi-graph G via a natural Cartesian product G1 × … × Gk having the same polynomial (partition) as G. Other results include an elementary sufficient condition for arbitrary nonnegative integral polynomials to be graphical.  相似文献   

10.
The concept of degree distance of a connected graph G is a variation of the well-known Wiener index, in which the degrees of vertices are also involved. It is defined by D(G)=∑xV(G)d(x)∑yV(G)d(x,y), where d(x) and d(x,y) are the degree of x and the distance between x and y, respectively. In this paper it is proved that connected graphs of order n≥4 having the smallest degree distances are K1,n−1,BS(n−3,1) and K1,n−1+e (in this order), where BS(n−3,1) denotes the bistar consisting of vertex disjoint stars K1,n−3 and K1,1 with central vertices joined by an edge.  相似文献   

11.
In this paper we determine which polynomials over ordered fields have multiples with nonnegative coefficients and also which polynomials can be written as quotients of two polynomials with nonnegative coefficients. This problem is related to a result given by Pólya in [G.H. Hardy, J.E. Littlewood, G. Pólya, Inequalities, Cambridge University Press, Cambridge, England, 1952] (as a companion of Artin’s theorem) that asserts that if F(X1,…,Xn)∈R[X1,…,Xn] is a form (i.e., a homogeneous polynomial) s.t.  with ∑xj>0, then F=G/H, where G,H are forms with all coefficients positive (i.e., every monomial of degree degG or degH appears in G or H, resp., with a coefficient that is strictly positive). In Pólya’s proof H is chosen to be H=(X1+?+Xn)m for some m.At the end we give some applications, including a generalization of Pólya’s result to arbitrary ordered fields.  相似文献   

12.
The restricted connectivity κ(G) of a connected graph G is defined as the minimum cardinality of a vertex-cut over all vertex-cuts X such that no vertex u has all its neighbors in X; the superconnectivity κ1(G) is defined similarly, this time considering only vertices u in G-X, hence κ1(G)?κ(G). The minimum edge-degree of G is ξ(G)=min{d(u)+d(v)-2:uvE(G)}, d(u) standing for the degree of a vertex u. In this paper, several sufficient conditions yielding κ1(G)?ξ(G) are given, improving a previous related result by Fiol et al. [Short paths and connectivity in graphs and digraphs, Ars Combin. 29B (1990) 17-31] and guaranteeing κ1(G)=κ(G)=ξ(G) under some additional constraints.  相似文献   

13.
The non-commuting graph ΓG of a non-abelian group G is defined as follows. The vertex set of ΓG is GZ(G) where Z(G) denotes the center of G and two vertices x and y are adjacent if and only if xyyx. It has been conjectured that if G and H are two non-abelian finite groups such that ΓGΓH, then |G|=|H| and moreover in the case that H is a simple group this implies GH. In this paper, our aim is to prove the first part of the conjecture for all the finite non-abelian simple groups H. Then for certain simple groups H, we show that the graph isomorphism ΓGΓH implies GH.  相似文献   

14.
Given a graph H with a labelled subgraph G, a retraction of H to G is a homomorphism r:HG such that r(x)=x for all vertices x in G. We call G a retract of H. While deciding the existence of a retraction to a fixed graph G is NP-complete in general, necessary and sufficient conditions have been provided for certain classes of graphs in terms of holes, see for example Hell and Rival.For any integer k?2 we describe a collection of graphs that generate the variety ARk of graphs G with the property that G is a retract of H whenever G is a subgraph of H and no hole in G of size at most k is filled by a vertex of H. We also prove that ARkNUFk+1, where NUFk+1 is the variety of graphs that admit a near unanimity function of arity k+1.  相似文献   

15.
A graph G has the Median Cycle Property (MCP) if every triple (u0,u1,u2) of vertices of G admits a unique median or a unique median cycle, that is a gated cycle C of G such that for all i,j,k∈{0,1,2}, if xi is the gate of ui in C, then: {xi,xj}⊆IG(ui,uj) if ij, and dG(xi,xj)<dG(xi,xk)+dG(xk,xj). We prove that a netlike partial cube has the MCP if and only if it contains no triple of convex cycles pairwise having an edge in common and intersecting in a single vertex. Moreover a finite netlike partial cube G has the MCP if and only if G can be obtained from a set of even cycles and hypercubes by successive gated amalgamations, and equivalently, if and only if G can be obtained from K1 by a sequence of special expansions. We also show that the geodesic interval space of a netlike partial cube having the MCP is a Pash-Peano space (i.e. a closed join space).  相似文献   

16.
A reflexive graph is a simple undirected graph where a loop has been added at each vertex. If G and H are reflexive graphs and UV(H), then a vertex map f:UV(G) is called nonexpansive if for every two vertices x,yU, the distance between f(x) and f(y) in G is at most that between x and y in H. A reflexive graph G is said to have the extension property (EP) if for every reflexive graph H, every UV(H) and every nonexpansive vertex map f:UV(G), there is a graph homomorphism φf:HG that agrees with f on U. Characterizations of EP-graphs are well known in the mathematics and computer science literature. In this article we determine when exactly, for a given “sink”-vertex sV(G), we can obtain such an extension φf;s that maps each vertex of H closest to the vertex s among all such existing homomorphisms φf. A reflexive graph G satisfying this is then said to have the sink extension property (SEP). We then characterize the reflexive graphs with the unique sink extension property (USEP), where each such sink extensions φf;s is unique.  相似文献   

17.
The cartesian product of a graph G with K2 is called a prism over G. We extend known conditions for hamiltonicity and pancyclicity of the prism over a graph G to the cartesian product of G with paths, cycles, cliques and general graphs. In particular we give results involving cubic graphs and almost claw-free graphs.We also prove the following: Let G and H be two connected graphs. Let both G and H have a 2-factor. If Δ(G)≤g(H) and Δ(H)≤g(G) (we denote by g(F) the length of a shortest cycle in a 2-factor of a graph F taken over all 2-factorization of F), then GH is hamiltonian.  相似文献   

18.
The problem examined in this paper comes from percolation theory. G = (X, E) is a simple geometric planar graph each vertex of which has a finite degree. We partition X in two subsets X1, X2 and we colour in blue each vertex and edge of the subgraph Gx generated by X1 and in red each vertex and edge of Gx2. We obtain blue clusters (resp. red clusters) namely the components of Gx1 (resp. of Gx2). We want to characterize G so that for any such coloration, any finite cluster of one colour is surrounded by a cluster of the other colour. A necessary and sufficient condition is that every component of G is a maximal infinite planar graph and that every vertex x is surrounded by the cycle which connects the vertices adjacent to x.  相似文献   

19.
If sk denotes the number of stable sets of cardinality k in graph G, and α(G) is the size of a maximum stable set, then is the independence polynomial of G [I. Gutman, F. Harary, Generalizations of the matching polynomial, Utilitas Math. 24 (1983) 97-106]. A graph G is very well-covered [O. Favaron, Very well-covered graphs, Discrete Math. 42 (1982) 177-187] if it has no isolated vertices, its order equals 2α(G) and it is well-covered, i.e., all its maximal independent sets are of the same size [M.D. Plummer, Some covering concepts in graphs, J. Combin. Theory 8 (1970) 91-98]. For instance, appending a single pendant edge to each vertex of G yields a very well-covered graph, which we denote by G*. Under certain conditions, any well-covered graph equals G* for some G [A. Finbow, B. Hartnell, R.J. Nowakowski, A characterization of well-covered graphs of girth 5 or greater, J. Combin. Theory Ser B 57 (1993) 44-68].The root of the smallest modulus of the independence polynomial of any graph is real [J.I. Brown, K. Dilcher, R.J. Nowakowski, Roots of independence polynomials of well-covered graphs, J. Algebraic Combin. 11 (2000) 197-210]. The location of the roots of the independence polynomial in the complex plane, and the multiplicity of the root of the smallest modulus are investigated in a number of articles.In this paper we establish formulae connecting the coefficients of I(G;x) and I(G*;x), which allow us to show that the number of roots of I(G;x) is equal to the number of roots of I(G*;x) different from -1, which appears as a root of multiplicity α(G*)-α(G) for I(G*;x). We also prove that the real roots of I(G*;x) are in [-1,-1/2α(G*)), while for a general graph of order n we show that its roots lie in |z|>1/(2n-1).Hoede and Li [Clique polynomials and independent set polynomials of graphs, Discrete Math. 125 (1994) 219-228] posed the problem of finding graphs that can be uniquely defined by their clique polynomials (clique-unique graphs). Stevanovic [Clique polynomials of threshold graphs, Univ. Beograd Publ. Elektrotehn. Fac., Ser. Mat. 8 (1997) 84-87] proved that threshold graphs are clique-unique. Here, we demonstrate that the independence polynomial distinguishes well-covered spiders among well-covered trees.  相似文献   

20.
A graph G homogeneously embeds in a graph H if for every vertex x of G and every vertex y of H there is an induced copy of G in H with x at y. The graph G uniformly embeds in H if for every vertex y of H there is an induced copy of G in H containing y. For positive integer k, let fk(G) (respectively, gk(G)) be the minimum order of a graph H whose edges can be k-coloured such that for each colour, G homogeneously embeds (respectively, uniformly embeds) in the graph given by V(H) and the edges of that colour. We investigate the values f2(G) and g2(G) for special classes of G, in particular when G is a star or balanced complete bipartite graph. Then we investigate fk(G) and gk(G) when k ≥ 3 and G is a complete graph.  相似文献   

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

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