共查询到19条相似文献,搜索用时 93 毫秒
1.
2.
3.
4.
无K4—图子式的图的谱半径 总被引:1,自引:0,他引:1
G是一个无K4-图子式、顶点数为n的简单图,ρ(G)是图G的谱半径。本文得出一个关于ρ(G)的上解界。ρ(G)≤1/2 √2n-15/4。等式成立当且仅当G≌K2倒△(n-2)K1,其中G1倒△G2是由G1∪G2组成,并且G1中的第一个点和G2中的每一个点之间都有一定边相连:(n-2)K1表示(n-2)个孤立点的集合。 相似文献
5.
图的扩张与稀疏矩阵计算中的若干优化问题 总被引:5,自引:1,他引:4
本文研究从稀疏矩阵计算中提出的若干离散最优化问题,即带宽,树宽,路宽,侧廓,扩充侧廓及填充问题。实际上,它们是一类图扩张问题;这些问题同时来源于各式各样的课题,如图子式理论,VLSI电路设计,互联网络及分子生物学等,本文从图论观点着重讨论两种统一途径:图的标号及图的扩张。 相似文献
6.
本文研究Brauer代数的根基问题.利用图子式的方法,获得了Gavarini的猜想对Brauer代数B1n是成立的结果. 相似文献
7.
8.
蒋忠樟 《数学年刊A辑(中文版)》2006,(2)
文[2]证明了实对称正定矩阵的子式阵仍然是实对称正定矩阵,文[3]给出了一般的正定矩阵的的概念,本文利用标准型给出了一般正定矩阵的子式阵仍然是正定矩阵的充要条件. 相似文献
9.
10.
G是一个无K4-图子式、顶点数为n的简单图,p(G)是图G的谱半径.本文得出一个关于p(G)的上确界:等式成立当且仅当 G ≌K2 (n-2)K1,其中 G1 G2是由 G1∪G2组成、并且G1中的第一个点和G2中的每一个点之间都有一条边相连:(n-2)K1表示(n-2)个孤立点的集合. 相似文献
11.
The class of planar graphs has unbounded treewidth, since the k×k grid, ∀k∈N, is planar and has treewidth k. So, it is of interest to determine subclasses of planar graphs which have bounded treewidth. In this paper, we show that if G is an even-hole-free planar graph, then it does not contain a 9×9 grid minor. As a result, we have that even-hole-free planar graphs have treewidth at most 49. 相似文献
12.
图G的弦图扩充问题包含两个问题:图G的最小填充问题和树宽问题,分别表示为f(G)和TW(G);图G的区间图扩充问题也包含两个问题:侧廓问题和路宽问题,分别表示为P(G)和PW(G).对一般图而言,它们都是NP-困难问题.一些特殊图类的填充数、树宽、侧廓问题和路宽具体值已被求出.主要研究树T的线图L(T)的弦图扩充问题;其次涉及到了两类特殊树—毛虫树和直径为4的树的线图的区间图扩充问题. 相似文献
13.
We prove that any H-minor-free graph, for a fixed graph H, of treewidth w has an Ω(w) × Ω(w) grid graph as a minor. Thus grid minors suffice to certify that H-minorfree graphs have large treewidth, up to constant factors. This strong relationship was previously known for the special
cases of planar graphs and bounded-genus graphs, and is known not to hold for general graphs. The approach of this paper can
be viewed more generally as a framework for extending combinatorial results on planar graphs to hold on H-minor-free graphs for any fixed H. Our result has many combinatorial consequences on bidimensionality theory, parameter-treewidth bounds, separator theorems,
and bounded local treewidth; each of these combinatorial results has several algorithmic consequences including subexponential
fixed-parameter algorithms and approximation algorithms.
A preliminary version of this paper appeared in the ACM-SIAM Symposium on Discrete Algorithms (SODA 2005) [16]. 相似文献
14.
Consider a drawing of a graph G in the plane such that crossing edges are coloured differently. The minimum number of colours,
taken over all drawings of G, is the classical graph parameter thickness. By restricting the edges to be straight, we obtain
the geometric thickness. By additionally restricting the vertices to be in convex position, we obtain the book thickness.
This paper studies the relationship between these parameters and treewidth. Our first main result states that for graphs of
treewidth k, the maximum thickness and the maximum geometric thickness both equal ⌈k/2⌉. This says that the lower bound for
thickness can be matched by an upper bound, even in the more restrictive geometric setting. Our second main result states
that for graphs of treewidth k, the maximum book thickness equals k if k ≤ 2 and equals k + 1 if k ≥ 3. This refutes a conjecture
of Ganley and Heath [Discrete Appl. Math. 109(3):215-221, 2001]. Analogous results are proved for outerthickness, arboricity,
and star-arboricity. 相似文献
15.
Brian Lucena 《Discrete Applied Mathematics》2007,155(8):1055-1065
One consequence of the graph minor theorem is that for every k there exists a finite obstruction set Obs(TW?k). However, relatively little is known about these sets, and very few general obstructions are known. The ones that are known are the cliques, and graphs which are formed by removing a few edges from a clique. This paper gives several general constructions of minimal forbidden minors which are sparse in the sense that the ratio of the treewidth to the number of vertices n does not approach 1 as n approaches infinity. We accomplish this by a novel combination of using brambles to provide lower bounds and achievable sets to demonstrate upper bounds. Additionally, we determine the exact treewidth of other basic graph constructions which are not minimal forbidden minors. 相似文献
16.
In recent articles by Grohe and Marx, the treewidth of the line graph of a complete graph is a critical example—in a certain sense, every graph with large treewidth “contains” . However, the treewidth of was not determined exactly. We determine the exact treewidth of the line graph of a complete graph. 相似文献
17.
18.
In 1977, Trotter and Moore proved that a poset has dimension at most 3 whenever its cover graph is a forest, or equivalently, has treewidth at most 1. On the other hand, a well-known construction of Kelly shows that there are posets of arbitrarily large dimension whose cover graphs have treewidth 3. In this paper we focus on the boundary case of treewidth 2. It was recently shown that the dimension is bounded if the cover graph is outerplanar (Felsner, Trotter, and Wiechert) or if it has pathwidth 2 (Biró, Keller, and Young). This can be interpreted as evidence that the dimension should be bounded more generally when the cover graph has treewidth 2. We show that it is indeed the case: Every such poset has dimension at most 1276. 相似文献
19.
Hans L. Bodlaender Dimitrios M. Thilikos 《Journal of Algorithms in Cognition, Informatics and Logic》1999,32(2):167
In this paper we investigate both the structure of graphs with branchwidth at most three, as well as algorithms to recognise such graphs. We show that a graph has branchwidth at most three if and only if it has treewidth at most three and does not contain the three-dimensional binary cube graph as a minor. A set of four graphs is shown to be the obstruction set for the class of graphs with branchwidth at most three. Moreover, we give a safe and complete set of reduction rules for the graphs with branchwidth at most three. Using this set, a linear time algorithm is given that verifies if a given graph has branchwidth at most three, and, if so, outputs a minimum width branch decomposition. 相似文献