首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 187 毫秒
1.
A biclique of a graph G is a maximal induced complete bipartite subgraph of G. Given a graph G, the biclique matrix of G is a {0,1,?1} matrix having one row for each biclique and one column for each vertex of G, and such that a pair of 1, ?1 entries in a same row corresponds exactly to adjacent vertices in the corresponding biclique. We describe a characterization of biclique matrices, in similar terms as those employed in Gilmore's characterization of clique matrices. On the other hand, the biclique graph of a graph is the intersection graph of the bicliques of G. Using the concept of biclique matrices, we describe a Krausz‐type characterization of biclique graphs. Finally, we show that every induced P3 of a biclique graph must be included in a diamond or in a 3‐fan and we also characterize biclique graphs of bipartite graphs. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 1–16, 2010  相似文献   

2.
If G is a bipartite graph with bipartition A, B then let Gm,n(A, B) be obtained from G by replacing each vertex a of A by an independent set a1, …, am, each vertex b of B by an independent set b1,…, bn, and each edge ab of G by the complete bipartite graph with edges aibj (1 ≤ i ≤ m and 1 ≤ j ≤ n). Whenever G has certain types of spanning forests, then cellular embeddings of G in surfaces S may be lifted to embeddings of Gm,n(A, B) having faces of the same sizes as those of G in S. These results are proved by the technique of “excess-current graphs.” They include new genus embeddings for a large class of bipartite graphs.  相似文献   

3.
Let ? be a symmetric binary function, positive valued on positive arguments. A graph G = (V,E) is a ?‐tolerance graph if each vertex υ ∈ V can be assigned a closed interval Iυ and a positive tolerance tυ so that xyE ? | IxIy|≥ ? (tx,ty). An Archimedean function has the property of tending to infinity whenever one of its arguments tends to infinity. Generalizing a known result of [15] for trees, we prove that every graph in a large class (which includes all chordless suns and cacti and the complete bipartite graphs K2,k) is a ?‐tolerance graph for all Archimedean functions ?. This property does not hold for most graphs. Next, we present the result that every graph G can be represented as a ?G‐tolerance graph for some Archimedean polynomial ?G. Finally, we prove that there is a ?universal”? Archimedean function ? * such that every graph G is a ?*‐tolerance graph. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 179–194, 2002  相似文献   

4.
For two integers a and b, we say that a bipartite graph G admits an (a, b)-bipartition if G has a bipartition (X, Y) such that |X| = a and |Y| = b. We say that two bipartite graphs G and H are compatible if, for some integers a and b, both G and H admit (a, b)-bipartitions. In this note, we prove that any two compatible trees of order n can be packed into a complete bipartite graph of order at most n + 1. We also provide a family of infinitely many pairs of compatible trees which cannot be packed into a complete bipartite graph of the same order. A theorem about packing two forests into a complete bipartite graph is derived from this result. © 1996 John Wiley & Sons, Inc.  相似文献   

5.
Let G be a finite simple graph on a vertex set V(G) = {x 11,…, x n1}. Also let m 1,…, m n  ≥ 2 be integers and G 1,…, G n be connected simple graphs on the vertex sets V(G i ) = {x i1,…, x im i }. In this article, we provide necessary and sufficient conditions on G 1,…, G n for which the graph obtained by attaching the G i to G is unmixed or vertex decomposable. Then we characterize Cohen–Macaulay and sequentially Cohen–Macaulay graphs obtained by attaching the cycle graphs or connected chordal graphs to arbitrary graphs.  相似文献   

6.
The boxicity of a graph G is defined as the minimum integer k such that G is an intersection graph of axis-parallel k-dimensional boxes. Chordal bipartite graphs are bipartite graphs that do not contain an induced cycle of length greater than 4. It was conjectured by Otachi, Okamoto and Yamazaki that chordal bipartite graphs have boxicity at most 2. We disprove this conjecture by exhibiting an infinite family of chordal bipartite graphs that have unbounded boxicity.  相似文献   

7.
We prove that a triangle-free graph G is a tolerance graph if and only if there exists a set of consecutively ordered stars that partition the edges of G. Since tolerance graphs are weakly chordal, a tolerance graph is bipartite if and only if it is triangle-free. We, therefore, characterize those tolerance graphs that are also bipartite. We use this result to show that in general, the class of interval bigraphs properly contains tolerance graphs that are triangle-free (and hence bipartite).  相似文献   

8.
Let G be a bipartite graph, with k|e(G). The zero-sum bipartite Ramsey number B(G, Zk) is the smallest integer t such that in every Zk-coloring of the edges of Kt,t, there is a zero-sum mod k copy of G in Kt,t. In this article we give the first proof that determines B(G, Z2) for all possible bipartite graphs G. In fact, we prove a much more general result from which B(G, Z2) can be deduced: Let G be a (not necessarily connected) bipartite graph, which can be embedded in Kn,n, and let F be a field. A function f : E(Kn,n) → F is called G-stable if every copy of G in Kn,n has the same weight (the weight of a copy is the sum of the values of f on its edges). The set of all G-stable functions, denoted by U(G, Kn,n, F) is a linear space, which is called the Kn,n uniformity space of G over F. We determine U(G, Kn,n, F) and its dimension, for all G, n and F. Utilizing this result in the case F = Z2, we can compute B(G, Z2), for all bipartite graphs G. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 151–166, 1998  相似文献   

9.
The basis number of a graph G was defined by Schmeichel to be the least integer h such that G has an h-fold basis for its cycle space. He proved that for m, n 5, the basis number b(K m,n ) of the complete bipartite graph K m,n is equal to 4 except for K 6,10, K 5,n and K 6,n with n = 5, 6, 7, 8. We determine the basis number of some particular non-planar graphs such as K 5,n and K 6,n , n = 5, 6, 7, 8, and r-cages for r = 5, 6, 7, 8, and the Robertson graph.  相似文献   

10.
In 1, we have previously observed that, in a chordal graph G, the maximum number of independent r-cliques (i.e., of vertex disjoint subgraphs of G, each isomorphic to Kr, with no edges joining any two of the subgraphs) equals the minimum number of cliques of G that meet all the r-cliques of G. When r = 1, this says that chordal graphs have independence number equal to the clique covering number. When r = 2, this is equivalent to a result of Cameron (1989), and it implies a well known forbidden subgraph characterization of split graphs. In this paper we consider a weighted version of the above min-max optimization problem. Given a chordal graph G, with a nonnegative weight for each r-clique in G, we seek a set of independent r-cliques with maximum total weight. We present two algorithms to solve this problem, based on the principle of complementary slackness. The first one operates on a graph derived from G, and is an adaptation of an algorithm of Farber (1982). The second one improves the performance by reducing the number of constraints of the linear programs. Both results produce a min-max relation. When the algorithms are specialized to the situation in which all the r-cliques have the same weight, we simplify the algorithms reported in 1, although these simpler algorithms are not as efficient. As a byproduct, we also obtain new elementary proofs of the above min-max result.  相似文献   

11.
Zhu, Li and Deng introduced in 1989 the definition of implicit degree of a vertex v in a graph G, denoted by id(v), by using the degrees of the vertices in its neighborhood and the second neighborhood. And they obtained sufficient conditions with implicit degrees for a graph to be hamiltonian. In this paper, we prove that if G is a 2–connected graph of order n ≥ 3 such that id(v) ≥ n/2 for each vertex v of G, then G is pancyclic unless G is bipartite, or else n = 4r, r ≥ 2 and G is in a class of graphs F 4r defined in the paper.  相似文献   

12.
Golumbic, Kaplan, and Shamir [Graph sandwich problems, J. Algorithms 19 (1995) 449-473], in their paper on graph sandwich problems published in 1995, left the status of the sandwich problems for strongly chordal graphs and chordal bipartite graphs open. It was recently shown [C.M.H. de Figueiredo, L. Faria, S. Klein, R. Sritharan, On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs, Theoret. Comput. Sci., accepted for publication] that the sandwich problem for strongly chordal graphs is NP-complete. We show that given graph G with a proper vertex coloring c, determining whether there is a supergraph of G that is chordal bipartite and also is properly colored by c is NP-complete. This implies that the sandwich problem for chordal bipartite graphs is also NP-complete.  相似文献   

13.
Chain graphs are exactly bipartite graphs without induced 2K 2 (a graph with four vertices and two disjoint edges). A graph G=(V,E) with a given independent set SV (a set of pairwise non-adjacent vertices) is said to be a chain partitioned probe graph if G can be extended to a chain graph by adding edges between certain vertices in S. In this note we give two characterizations for chain partitioned probe graphs. The first one describes chain partitioned probe graphs by six forbidden subgraphs. The second one characterizes these graphs via a certain “enhanced graph”: G is a chain partitioned probe graph if and only if the enhanced graph G * is a chain graph. This is analogous to a result on interval (respectively, chordal, threshold, trivially perfect) partitioned probe graphs, and gives an O(m 2)-time recognition algorithm for chain partitioned probe graphs.  相似文献   

14.
A minimal blocker in a bipartite graph G is a minimal set of edges the removal of which leaves no perfect matching in G. We give an explicit characterization of the minimal blockers of a bipartite graph G. This result allows us to obtain a polynomial delay algorithm for finding all minimal blockers of a given bipartite graph. Equivalently, we obtain a polynomial delay algorithm for listing the anti‐vertices of the perfect matching polytope of G. We also provide generation algorithms for other related problems, including d‐factors in bipartite graphs, and perfect 2‐matchings in general graphs. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 209–232, 2006  相似文献   

15.
Let X be a nonempty set of positive integers and X* = X?{1}. The divisibility graph D(X) has X* as the vertex set, and there is an edge connecting a and b with a, b ∈ X* whenever a divides b or b divides a. Let X = cs(G) be the set of conjugacy class sizes of a group G. In this case, we denote D(cs(G)) by D(G). In this paper, we will find the number of connected components of D(G) where G is the symmetric group S n or is the alternating group A n .  相似文献   

16.
A graph G on n vertices is said to be separable cost constant Hamiltonian (SC-Hamiltonian) if and only if G is Hamiltonian and for any cost matrix C=(c(i,j)) associated with G where all tours have the same cost, there exist vectors a=(a1,…,an) and b=(b1,…,bn) such that . In this paper we show that for symmetric digraphs strong Hamiltonicity is a necessary condition for SC-Hamiltonicity. As a surprising consequence, we prove that the symmetric digraph obtained from an undirected SC-Hamiltonian graph by edge duplication need not be SC-Hamiltonian. This settles a conjecture of Kabadi and Punnen. We then show that an undirected graph on an even number of nodes having an edge that appears in every Hamiltonian cycle cannot be SC-Hamiltonian. Using this we establish that multiple subdivision of an edge need not preserve SC-Hamiltonicity, disproving a previous claim. Further, we identify other necessary conditions for SC-Hamiltonicity and obtain new classes of SC-Hamiltonian graphs.  相似文献   

17.
A graph H is called a supersubdivison of a graph G if H is obtained from G by replacing every edge uv of G by a complete bipartite graph K2,m (m may vary for each edge) by identifying u and v with the two vertices in K2,m that form one of the two partite sets. We denote the set of all such supersubdivision graphs by SS(G). Then, we prove the following results.
1. Each non-trivial connected graph G and each supersubdivision graph HSS(G) admits an α-valuation. Consequently, due to the results of Rosa (in: Theory of Graphs, International Symposium, Rome, July 1966, Gordon and Breach, New York, Dunod, Paris, 1967, p. 349) and El-Zanati and Vanden Eynden (J. Combin. Designs 4 (1996) 51), it follows that complete graphs K2cq+1 and complete bipartite graphs Kmq,nq can be decomposed into edge disjoined copies of HSS(G), for all positive integers m,n and c, where q=|E(H)|.
2. Each connected graph G and each supersubdivision graph in SS(G) is strongly n-elegant, where n=|V(G)| and felicitous.
3. Each supersubdivision graph in EASS(G), the set of all even arbitrary supersubdivision graphs of any graph G, is cordial.
Further, we discuss a related open problem.  相似文献   

18.
Victor Guba 《代数通讯》2013,41(5):1988-1997
Let G be a group generated by a finite set A. An element g ∈ G is a strict dead end of depth k (with respect to A) if |g|>|ga 1|>|ga 1 a 2|>···>|ga 1 a 2a k | for any a 1, a 2,…, a k  ∈ A ±1 such that the word a 1 a 2a k is freely irreducible. (Here |g| is the distance from g to the identity in the Cayley graph of G.) We show that in finitely generated free soluble groups of degree d ≥ 2 there exist strict dead elements of depth k = k(d), which grows exponentially with respect to d.  相似文献   

19.
Anm-crown is the complete tripartite graphK 1, 1,m with parts of order 1, 1,m, and anm-claw is the complete bipartite graphK 1,m with parts of order 1,m, wherem ≥ 3. A vertexa of a graph Γ is calledweakly reduced iff the subgraph {x є Γ ‖a =x } consists of one vertex. A graph Γ is calledweakly reduced iff all its vertices are weakly reduced. In the present paper we classify all connected weakly reduced graphs without 3-crowns, all of whose μ-subgraphs are regular graphs of constant nonzero valency. In particular, we generalize the characterization of Grassman and Johnson graphs due to Numata, and the characterization of connected reduced graphs without 3-claws due to Makhnev. Translated fromMatematicheskie Zametki, Vol. 67, No. 6, pp. 874–881, June, 2000. This research was supported by the Russian Foundation for Basic Research under grant No. 99-01-00462.  相似文献   

20.
We prove that any complete bipartite graph K a,b , where a, b are even integers, can be decomposed into closed trails with prescribed even lengths.  相似文献   

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

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