首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 31 毫秒
1.
《Discrete Mathematics》2004,274(1-3):93-108
Fan Chung and Ron Graham (J. Combin. Theory Ser. B 65 (1995) 273–290) introduced the cover polynomial for a directed graph and showed that it was connected with classical rook theory. Dworkin (J. Combin. Theory Ser. B 71 (1997) 17–53) showed that the cover polynomial naturally factors for directed graphs associated with Ferrers boards. The authors (Adv. Appl. Math. 27 (2001) 438–481) developed a rook theory for shifted Ferrers boards where the analogue of a rook placement is replaced by a partial perfect matching of K2n, the complete graph on 2n vertices. In this paper, we show that an analogue of Dworkin's result holds for shifted Ferrers boards in this setting. We also show how cycle-counting matching numbers are connected to cycle-counting “hit numbers” (which involve perfect matchings of K2n).  相似文献   

2.
《Discrete Applied Mathematics》2002,116(1-2):115-126
For vertices u and v in an oriented graph D, the closed interval I[u,v] consists of u and v together with all vertices lying in a uv geodesic or vu geodesic in D. For SV(D), I[S] is the union of all closed intervals I[u,v] with u,vS. A set S is convex if I[S]=S. The convexity number con(D) is the maximum cardinality of a proper convex set of V(D). The nontrivial connected oriented graphs of order n with convexity number n−1 are characterized. It is shown that there is no connected oriented graph of order at least 4 with convexity number 2 and that every pair k, n of integers with 1⩽kn−1 and k≠2 is realizable as the convexity number and order, respectively, of some connected oriented graph. For a nontrivial connected graph G, the lower orientable convexity number con(G) is the minimum convexity number among all orientations of G and the upper orientable convexity number con+(G) is the maximum such convexity number. It is shown that con+(G)=n−1 for every graph G of order n⩾2. The lower orientable convexity numbers of some well-known graphs are determined, with special attention given to outerplanar graphs.  相似文献   

3.
Let K(G) for a finite graph G with vertices v1,...,vn denote the K-algebra with generators X1,...,Xn and defining relations XiXj=XjXi if and only if vi is not connected to vj by an edge in G. We describe centralizers of monomials, show that the centralizer of a monomial is again a graph algebra, prove a unique factorization theorem for factorizations of monomials into commuting factors, compute the homology of K(G), and show that K(G) is the homology ring of a certain loop space. We also construct a K(π, 1) explicitly where π is the group with generators X1,...,Xn and defining relations XiXj=XjXi if and only if vi is not connected to vj by an edge in G.  相似文献   

4.
Let N(n,i) = (k,…,kn,n?ik)ci/i, i = O.…,[n/k]. We prove that the random variable Xn such that P(Xn = i) = N(n, i)Σj N(n, j) has asymptotically (n → ∞) a normal distribution and we give some combinatorial applications of this result.We also improve a result of Godsil [3] dealing with matchings in graph.  相似文献   

5.
The distance d G (u, v) between two vertices u and v in a connected graph G is the length of the shortest uv-path in G. A uv-path of length d G (u, v) is called a uv-geodesic. A set X is convex in G if vertices from all ab-geodesics belong to X for any two vertices a, b ?? X. The convex domination number ??con(G) of a graph G equals the minimum cardinality of a convex dominating set. In the paper, Nordhaus-Gaddum-type results for the convex domination number are studied.  相似文献   

6.
There are only few results concerning crossing numbers of join of some graphs. In the paper, for the special graph H on six vertices we give the crossing numbers of its join with n isolated vertices as well as with the path Pn on n vertices and with the cycle Cn.  相似文献   

7.
A noncomplete graph G is called an (n, k)‐graph if it is n‐connected and GX is not (n − |X| + 1)‐connected for any XV(G) with |X| ≤ k. Mader conjectured that for k ≥ 3 the graph K2k + 2 − (1‐factor) is the unique (2k, k)‐graph. We settle this conjecture for strongly regular graphs, for edge transitive graphs, and for vertex transitive graphs. © 2000 John Wiley & Sons, Inc. J Graph Theory 36: 35–51, 2001  相似文献   

8.
Let D be a connected oriented graph. A set SV(D) is convex in D if, for every pair of vertices x,yS, the vertex set of every x-y geodesic (x-y shortest dipath) and y-x geodesic in D is contained in S. The convexity numbercon(D) of a nontrivial oriented graph D is the maximum cardinality of a proper convex set of D. Let G be a graph. We define that SC(G)={con(D):D is an orientation of G} and SSC(G)={con(D):D is a strongly connected orientation of G}. In the paper, we show that, for any n?4, 1?a?n-2, and a≠2, there exists a 2-connected graph G with n vertices such that SC(G)=SSC(G)={a,n-1} and there is no connected graph G of order n?3 with SSC(G)={n-1}. Then, we determine that SC(K3)={1,2}, SC(K4)={1,3}, SSC(K3)=SSC(K4)={1}, SC(K5)={1,3,4}, SC(K6)={1,3,4,5}, SSC(K5)=SSC(K6)={1,3}, SC(Kn)={1,3,5,6,…,n-1}, SSC(Kn)={1,3,5,6,…,n-2} for n?7. Finally, we prove that, for any integers n, m, and k with , 1?k?n-1, and k≠2,4, there exists a strongly connected oriented graph D with n vertices, m edges, and convexity number k.  相似文献   

9.
The celebrated result of Fleischner states that the square of every 2-connected graph is Hamiltonian. We investigate what happens if the graph is just connected. For every n ≥ 3, we determine the smallest length c(n) of a longest cycle in the square of a connected graph of order n and show that c(n) is a logarithmic function in n. Furthermore, for every c ≥ 3, we characterize the connected graphs of largest order whose square contains no cycle of length at least c.  相似文献   

10.
The disconnection number d(X) is the least number of points in a connected topological graph X such that removal of d(X) points will disconnect X (Nadler, 1993 [6]). Let Dn denote the set of all homeomorphism classes of topological graphs with disconnection number n. The main result characterizes the members of Dn+1 in terms of four possible operations on members of Dn. In addition, if X and Y are topological graphs and X is a subspace of Y with no endpoints, then d(X)?d(Y) and Y obtains from X with exactly d(Y)−d(X) operations. Some upper and lower bounds on the size of Dn are discussed.The algorithm of the main result has been implemented to construct the classes Dn for n?8, to estimate the size of D9, and to obtain information on certain subclasses such as non-planar graphs (n?9) and regular graphs (n?10).  相似文献   

11.
In his paper [17], Sabidussi defined the X-join of a family of graphs. Cowan, James, Stanton gave in [6] and O(n4) algorithm that decomposes a graph, when possible, into the X-join of the family of its subgraphs. We give here another approach using an equivalence relation on the edge set of the graph. We prove that if G and its complement are connected then there exists an unique class of edges that covers all the vertices of G. This theorem yields immediately an O(n3) decomposition algorithm.  相似文献   

12.
Let Γ be an X‐symmetric graph admitting an X‐invariant partition ?? on V(Γ) such that Γ?? is connected and (X, 2)‐arc transitive. A characterization of (Γ, X, ??) was given in [S. Zhou Eur J Comb 23 (2002), 741–760] for the case where |B|>|Γ(C)∩B|=2 for an arc (B, C) of Γ??.We con‐sider in this article the case where |B|>|Γ(C)∩B|=3, and prove that Γ can be constructed from a 2‐arc transitive graph of valency 4 or 7 unless its connected components are isomorphic to 3 K 2, C 6 or K 3, 3. As a byproduct, we prove that each connected tetravalent (X, 2)‐transitive graph is either the complete graph K 5 or a near n‐gonal graph for some n?4. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 232–245, 2010  相似文献   

13.
Jia Huang 《Discrete Mathematics》2007,307(15):1881-1897
The bondage number b(G) of a nonempty graph G is the cardinality of a smallest edge set whose removal from G results in a graph with domination number greater than the domination number γ(G) of G. Kang and Yuan proved b(G)?8 for every connected planar graph G. Fischermann, Rautenbach and Volkmann obtained some further results for connected planar graphs. In this paper, we generalize their results to connected graphs with small crossing numbers.  相似文献   

14.
《Discrete Mathematics》1986,58(3):317-321
In [4] Jung and Watkins proved that for a connected infinite graph X either κ(X) = ∞ holds or X is a strip, if Aut(X) contains a transitive abelian subgroup G. Here we prove the same result under weaker assumptions.  相似文献   

15.
We construct a functor AC(?, ?) from the category of path connected spaces X with a base point x to the category of simply connected spaces. The following are the main results of the paper: (i) If X is a Peano continuum then AC(X, x) is a cell-like Peano continuum; (ii) If X is n-dimensional then AC(X, x) is (n + 1)?dimensional; and (iii) For a path connected space X, π 1(X, x) is trivial if and only if π 2(AC(X, x)) is trivial. As a corollary, AC(S 1, x) is a 2-dimensional nonaspherical cell-like Peano continuum.  相似文献   

16.
We enumerate weighted simple graphs with a natural upper bound condition on the sum of the weight of adjacent vertices. We also compute the generating function of the numbers of these graphs, and prove that it is a rational function. In particular, we show that the generating function for connected bipartite simple graphs is of the form p1(x)/(1-x)m+1. For nonbipartite simple graphs, we get a generating function of the form p2(x)/(1-x)m+1(1+x)l. Here m is the number of vertices of the graph, p1(x) is a symmetric polynomial of degree at most m, p2(x) is a polynomial of degree at most m+l, and l is a nonnegative integer. In addition, we give computational results for various graphs.  相似文献   

17.
We denote by SG n,k the stable Kneser graph (Schrijver graph) of stable n-subsets of a set of cardinality 2n+k. For k≡3 (mod 4) and n≥2 we show that there is a component of the χ-colouring graph of SG n,k which is invariant under the action of the automorphism group of SG n,k . We derive that there is a graph G with χ(G)=χ(SG n,k ) such that the complex Hom(SG n,k ,G) is non-empty and connected. In particular, for k≡3 (mod 4) and n≥2 the graph SG n,k is not a test graph.  相似文献   

18.
For an ordered set W = {w 1, w 2,..., w k} of vertices and a vertex v in a connected graph G, the representation of v with respect to W is the k-vector r(v|W) = (d(v, w 1), d(v, w 2),... d(v, w k)), where d(x, y) represents the distance between the vertices x and y. The set W is a resolving set for G if distinct vertices of G have distinct representations with respect to W. A resolving set for G containing a minimum number of vertices is a basis for G. The dimension dim(G) is the number of vertices in a basis for G. A resolving set W of G is connected if the subgraph 〈W〉 induced by W is a nontrivial connected subgraph of G. The minimum cardinality of a connected resolving set in a graph G is its connected resolving number cr(G). Thus 1 ≤ dim(G) ≤ cr(G) ≤ n?1 for every connected graph G of order n ≥ 3. The connected resolving numbers of some well-known graphs are determined. It is shown that if G is a connected graph of order n ≥ 3, then cr(G) = n?1 if and only if G = K n or G = K 1,n?1. It is also shown that for positive integers a, b with ab, there exists a connected graph G with dim(G) = a and cr(G) = b if and only if $\left( {a,b} \right) \notin \left\{ {\left( {1,k} \right):k = 1\;{\text{or}}\;k \geqslant 3} \right\}$ Several other realization results are present. The connected resolving numbers of the Cartesian products G × K 2 for connected graphs G are studied.  相似文献   

19.
We say that two graphs G1 and G2 with the same vertex set commute if their adjacency matrices commute. In this paper, we find all integers n such that the complete bipartite graph Kn,n is decomposable into commuting perfect matchings or commuting Hamilton cycles. We show that there are at most n−1 linearly independent commuting adjacency matrices of size n; and if this bound occurs, then there exists a Hadamard matrix of order n. Finally, we determine the centralizers of some families of graphs.  相似文献   

20.
We investigate the list-chromatic number of infinite graphs. It is easy to see that Chr(X) ≤ List(X) ≤ Col(X) for each graph X. It is consistent that List(X) = Col(X) holds for every graph with Col(X) infinite. It is also consistent that for graphs of cardinality ? 1, List(X) is countable iff Chr(X) is countable.  相似文献   

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

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