共查询到20条相似文献,搜索用时 343 毫秒
1.
2.
Erich Prisner 《Combinatorica》2000,20(1):109-117
Bicliques are inclusion-maximal induced complete bipartite subgraphs in graphs. Upper bounds on the number of bicliques in bipartite
graphs and general graphs are given. Then those classes of graphs where the number of bicliques is polynomial in the vertex
number are characterized, provided the class is closed under induced subgraphs.
Received January 27, 1997 相似文献
3.
We introduce a new family of bipartite graphs which is the bipartite analogue of the class ofcomplement reduciblegraphs orcographs. Abi-complement reduciblegraph orbi-cographis a bipartite graphG = (W ∪ B, E) that can be reduced to single vertices by recursively bi-complementing the edge set of all connected bipartite subgraphs. Thebi-complementedgraphofGis the graph having the same vertex setW ∪ BasG, while its edge set is equal toW × B − E. The aim of this paper is to show that there exists an equivalent definition of bi-cographs by three forbidden configurations. We also propose a tree representation for this class of graphs. 相似文献
4.
N. P. Chiang 《Journal of Optimization Theory and Applications》2006,131(3):485-491
In this paper, we study the chaotic numbers of complete bipartite graphs and complete tripartite graphs. For the complete bipartite graphs, we find closed-form formulas of the chaotic numbers and characterize all chaotic mappings. For the complete tripartite graphs, we develop an algorithm running in O(n
4
3) time to find the chaotic numbers, with n
3 the number of vertices in the largest partite set.Research supported by NSC 90-2115-M-036-003.The author thanks the authors of Ref. 6, since his work was motivated by their work. Also, the author thanks the referees for helpful comments which made the paper more readable. 相似文献
5.
6.
We define two types of bipartite graphs, chordal bipartite graphs and perfect elimination bipartite graphs, and prove theorems analogous to those of Dirac and Rose for chordal graphs (rigid circuit graphs, triangulated graphs). Our results are applicable to Gaussian elimination on sparse matrices where a sequence of pivots preserving zeros is sought. Our work removes the constraint imposed by Haskins and Rose that pivots must be along the main diagonal. 相似文献
7.
一个图的特征值通常指的是它的邻接矩阵的特征值,在图的所有特征值中,重数为1的特征值即所谓的单特征值具有特殊的重要性.确定一个图的单特征值是一个比较困难的问题,主要是没有一个通用的方法.1969年,Petersdorf和Sachs给出了点传递图单特征值的取值范围,但是对于具体的点传递图还需要根据图本身的特性来确定它的单特征值.给出一类正则二部图,它们是二面体群的凯莱图,这类图的单特征值中除了它的正、负度数之外还有0或者±1,而它们恰好是Petersdorf和Sachs所给出的单特征值范围内的中间取值. 相似文献
8.
一个图G的路分解是指一路集合使得G的每条边恰好出现在其中一条路上.记Pl长度为l-1的路,如果G能够分解成若干个Pl,则称G存在{Pl}—分解.关于图的给定长路分解问题主要结果有:(i)连通图G存在{P3}—分解当且仅当G有偶数条边(见[1]);(ii)连通图G存在{P3,P4}—分解当且仅当G不是C3和奇树,这里C3的长度为3的圈而奇树是所有顶点皆度数为奇数的树(见[3]).本文讨论了3正则图的{P4}—分解情况,并构造证明了边数为3k(k热∈Z且k≥2)的完全图Kn和完全二部图Kr,s存在{P4}—分解. 相似文献
9.
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. 相似文献
10.
Recently Alon and Friedland have shown that graphs which are the union of complete regular bipartite graphs have the maximum number of 1-factors over all graphs with the same degree sequence. We identify two families of graphs that have the maximum number of 1-factors over all graphs with the same number of vertices and edges: the almost regular graphs which are unions of complete regular bipartite graphs, and complete graphs with a matching removed. The first family is determined using the Alon and Friedland bound. For the second family, we show that a graph transformation which is known to increase network reliability also increases the number of 1-factors. In fact, more is true: this graph transformation increases the number of k-factors for all k≥1, and “in reverse” also shows that in general, threshold graphs have the fewest k-factors. We are then able to determine precisely which threshold graphs have the fewest 1-factors. We conjecture that the same graphs have the fewest k-factors for all k≥2 as well. 相似文献
11.
We prove a necessary condition for polynomial solvability of the jump number problem in classes of bipartite graphs characterized by a finite set of forbidden induced bipartite subgraphs. For some classes satisfying this condition, we propose polynomial algorithms to solve the jump number problem. 相似文献
12.
13.
Pierre Aboulker Marko Radovanović Nicolas Trotignon Théophile Trunck Kristina Vušković 《Journal of Graph Theory》2014,75(2):150-166
In Math Program 55(1992), 129–168, Conforti and Rao conjectured that every balanced bipartite graph contains an edge that is not the unique chord of a cycle. We prove this conjecture for balanced bipartite graphs that do not contain a cycle of length 4 (also known as linear balanced bipartite graphs), and for balanced bipartite graphs whose maximum degree is at most 3. We in fact obtain results for more general classes, namely linear balanceable and subcubic balanceable graphs. Additionally, we prove that cubic balanced graphs contain a pair of twins, a result that was conjectured by Morris, Spiga, and Webb in ( Discrete Math 310(2010), 3228–3235). 相似文献
14.
若图的邻点可区别全染色的各色所染元素数之差不超过1,则称该染色法为图的均匀邻点可区别全染色,而所用的最少颜色数称为该图的均匀邻点可区别全色数.本文给出了一类二部图的均匀邻点可区别全染色数. 相似文献
15.
We define a class of bipartite graphs that correspond
naturally with Ferrers diagrams. We give expressions for the
number of spanning trees, the number of Hamiltonian paths when
applicable, the chromatic polynomial and the chromatic symmetric
function. We show that the linear coefficient of the chromatic
polynomial is given by the excedance set statistic. 相似文献
16.
给定染色数的无符号Laplace谱半径 总被引:2,自引:0,他引:2
设Gkn(k≥2)为n阶的染色数为k的连通图的集合.本文确定了Gkn中具有极大无符号Laplace谱半径的图,即k=2时为完全二部图,k≥3时为Turn图.本文也讨论了Gkn中的具有极小无符号Laplace谱半径的图,对k≤3的情形给出了此类图的刻画. 相似文献
17.
Bouchet's conjecture asserts that each signed graph which admits a nowhere‐zero flow has a nowhere‐zero 6‐flow. We verify this conjecture for two basic classes of signed graphs—signed complete and signed complete bipartite graphs by proving that each such flow‐admissible graph admits a nowhere‐zero 4‐flow and we characterise those which have a nowhere‐zero 2‐flow and a nowhere‐zero 3‐flow. 相似文献
18.
19.
We determine the minimum size of n-factor-critical graphs and that of k-extendable bipartite graphs, by considering Harary graphs and related graphs. Moreover, we determine the minimum size of
k-extendable non-bipartite graphs for k = 1, 2, and pose a related conjecture for general k. 相似文献
20.
Jenö Lehel† 《Graphs and Combinatorics》1994,10(2-4):353-361
We show that the line graph of any balanced hypergraph is neighbourhood-perfect. This result is a hypergraphic extension of a recent theorem in [GKLM] saying that the line graphs of bipartite graphs are neighbourhood-perfect. The note contains also a graphical extension of the same theorem: the characterization of all graphs with neighbourhood-perfect line graph. The proof relies on a characterization of neighbourhood-perfect graphs among line graphs in terms of forbidden induced subgraphs. 相似文献