共查询到20条相似文献,搜索用时 0 毫秒
1.
Gbor N. Srkzy 《Journal of Graph Theory》1995,19(3):323-331
Let G = G(A, B) be a bipartite graph with |A| = u, |B| = v, and let / be a positive integer. In this paper we prove the following result: If v ≤ u, uv ≤ n, m = |E(G)|, and m ≥ max{180/u, 20/n1/2(1+(1/l))}, then G contains a C2/. © 1995 John Wiley & Sons, Inc. 相似文献
2.
3.
It is shown that if an oriented complete bipartite graph has a directed cycle of length 2n, then it has directed cycles of all smaller even lengths unless n is even and the 2n-cycle induces one special digraph. 相似文献
4.
Jochen Harant 《Discrete Mathematics》2009,309(1):113-122
We prove that the domination number of a graph of order n and minimum degree at least 2 that does not contain cycles of length 4, 5, 7, 10 or 13 is at most . Furthermore, we derive upper bounds on the domination number of bipartite graphs of given minimum degree. 相似文献
5.
6.
Franz Hering 《Israel Journal of Mathematics》1971,9(3):403-417
We investigate a class of bipartite graphs, whose structure is determined by a binary number.
The work for this research was supported by the Max Kade Foundation. 相似文献
7.
A graphoidal cover of a graph G is a collection ψ of (not necessarily open) paths inG such that every path in ψ has at least two vertices, every vertex ofG is an internal vertex of at most one path in ψ and every edge of G is in exactly one path in ψ. Let Ω (ψ) denote the intersection graph of ψ. A graph G is said to be graphoidal if there exists a graphH and a graphoidal cover ψof H such that G is isomorphic to Ω(ψ). In this paper we study the properties of graphoidal graphs and obtain a forbidden subgraph characterisation of bipartite graphoidal graphs. 相似文献
8.
Let G be a graph on the vertex set V={x
1, ..., x
n}. Let k be a field and let R be the polynomial ring k[x
1, ..., x
n]. The graph ideal
I(G), associated to G, is the ideal of R generated by the set of square-free monomials x
ixj so that x
i, is adjacent to x
j. The graph G is Cohen-Macaulay over k if R/I(G) is a Cohen-Macaulay ring.
Let G be a Cohen-Macaulay bipartite graph. The main result of this paper shows that G{v} is Cohen-Macaulay for some vertex v in G. Then as a consequence it is shown that the Reisner-Stanley simplicial complex of I(G) is shellable. An example of N. Terai is presented showing these results fail for Cohen-Macaulay non bipartite graphs.
Partially supported by COFAA-IPN, CONACyT and SNI, México. 相似文献
9.
Nigel Martin 《Discrete Mathematics》2006,306(17):2084-2090
We construct a new infinite family of factorizations of complete bipartite graphs by factors all of whose components are copies of a (fixed) complete bipartite graph Kp,q. There are simple necessary conditions for such factorizations to exist. The family constructed here demonstrates sufficiency in many new cases. In particular, the conditions are always sufficient when q=p+1. 相似文献
10.
We give a simple proof that everyk-connected bipartite tournament has a cycle through every set ofk vertices. This was conjectured in [4].This research was done while the first author was visiting Laboratoire de Recherche en Informatique, universite Paris-Sud whose hospitality and financial support is gratefully acknowledged 相似文献
11.
Bill Jackson 《Journal of Combinatorial Theory, Series B》1985,38(2):118-131
Let G be a 2-connected bipartite graph with bipartition (A, B), where |A| ≥ |B|. It is shown that if each vertex of A has degree at least k, and each vertex of B has degree at least l, then G contains a cycle of length at least 2min(|B|, k + l ? 1, 2k ? 2). Then this result is used to determine the minimum number of edges required in a bipartite graph to ensure a cycle of length at least 2m, for any integer m ≥ 2. 相似文献
12.
13.
《European Journal of Operational Research》2005,164(3):575-584
The theorem of König on edge colorings in bipartite multigraphs can be seen as the integral version of the theorem of Birkhoff and von Neumann on bistochastic matrices.Here we consider the more general case where the matrix A=(aij) to be decomposed has real entries (instead of non negative entries). We shall concentrate on the integral case. Interpretation in terms of arc and path colorings are given with some properties of these decompositions and one shows that some balancing problems which are trivial in the classical case are now NP-complete. We also introduce requirements on the parity of the paths in the decompositions. 相似文献
14.
Camino Balbuena Martín Cera Pedro García-Vázquez Juan Carlos Valenzuela 《数学学报(英文版)》2011,27(11):2085-2100
For a bipartite graph G on m and n vertices, respectively, in its vertices classes, and for integers s and t such that 2 ≤ s ≤ t, 0 ≤ m − s ≤ n − t, and m + n ≤ 2s + t − 1, we prove that if G has at least mn − (2(m − s) + n − t) edges then it contains a subdivision of the complete bipartite K
(s,t) with s vertices in the m-class and t vertices in the n-class. Furthermore, we characterize the corresponding extremal bipartite graphs with mn − (2(m − s) + n − t + 1) edges for this topological Turan type problem. 相似文献
15.
16.
Xiaoyun Lu 《Combinatorica》1995,15(2):247-254
We give a sufficient condition for bipartite graphs to be Hamiltonian. The condition involves the edge-density and balanced independence number of a bipartite graph. 相似文献
17.
18.
On bipartite zero-divisor graphs 总被引:1,自引:0,他引:1
A (finite or infinite) complete bipartite graph together with some end vertices all adjacent to a common vertex is called a complete bipartite graph with a horn. For any bipartite graph G, we show that G is the graph of a commutative semigroup with 0 if and only if it is one of the following graphs: star graph, two-star graph, complete bipartite graph, complete bipartite graph with a horn. We also prove that a zero-divisor graph is bipartite if and only if it contains no triangles. In addition, we give all corresponding zero-divisor semigroups of a class of complete bipartite graphs with a horn and determine which complete r-partite graphs with a horn have a corresponding semigroup for r≥3. 相似文献
19.
D.H. Smith 《Discrete Mathematics》1974,10(1):167-172
In this paper the determination of all distance-transitive graphs of valency four is completed. 相似文献
20.
Peter Allen 《Journal of Graph Theory》2009,60(3):219-241
Given a fixed bipartite graph H, we study the asymptotic speed of growth of the number of bipartite graphs on n vertices which do not contain an induced copy of H. Whenever H contains either a cycle or the bipartite complement of a cycle, the speed of growth is . For every other bipartite graph except the path on seven vertices, we are able to find both upper and lower bounds of the form . In many cases we are able to determine the correct value of c. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 219–241, 2009 相似文献