共查询到19条相似文献,搜索用时 93 毫秒
1.
本文基于不完备P-矩阵的1-通弦图和1-通弦块图的完成问题,获得了不完备正P-矩阵在一定条件下的k-通弦图和k-通弦块图的完成,同时解决了不完备正P-矩阵在k-通弦图和k-通弦块图下的逆零完成问题(k为大于1的整数). 相似文献
2.
设Kv是一个v点完全图,G是一个有限简单图,Kv上的一个图设计G-GD(v)是一个对子(X,B),其中X是Kv的顶点集合,B是Kv的一些与G同构的子图(称为区组)的集合,使得Kv的任意一条边恰出现在B的一个区组中.文中讨论的简单图是C(r)10,即带有一条弦的10长圈(含有11条边),其中r表示弦的两个端点之间的顶点个数,1≤r≤4.给出了C^(r)10-GD(v)的存在谱:v=0,1(mod11)且v≥11. 相似文献
3.
4.
5.
6.
7.
8.
9.
设Kv是一个v点完全图.G是一个有限简单图.Kv上的一个图设计G-GD是一个对子(X,B),其中X是Kv的顶点集合,B是Kv的一些与G同构的子图(称为区组)的集合,使得Kv的任意一条边恰出现在B的一个区组中.文中讨论的简单图是C^(r)2k,即带有一条弦的2k长圈,其中r表示弦的两个端点之间的顶点个数,1≤r≤k-1.文中给出了一个构作C^(r)m设计的统一方法,并得到关于v≡0,1(mod2k+1)时C^(r)2k-GD(v)的一系列结果. 相似文献
10.
我们知道,赵爽的"弦图(或勾股圆方图)"是由四个全等的直角三角形围成的,赵爽利用它巧妙地证明了勾股定理,其证法之优美、精巧,令人叹为观止,它是证明勾股定理最著名的证法之一,特别是"弦图"一图蕴含两种证法更是举世无双".弦图"是证明勾股定理的无字经典 相似文献
11.
An asteroidal triple is a stable set of three vertices such that each pair is connected by a path avoiding the neighborhood of the third vertex. Asteroidal triples play a central role in a classical characterization of interval graphs by Lekkerkerker and Boland. Their result says that a chordal graph is an interval graph if and only if it does not contain an asteroidal triple. In this paper, we prove an analogous theorem for directed path graphs which are the intersection graphs of directed paths in a directed tree. For this purpose, we introduce the notion of a special connection. Two non‐adjacent vertices are linked by a special connection if either they have a common neighbor or they are the endpoints of two vertex‐disjoint chordless paths satisfying certain conditions. A special asteroidal triple is an asteroidal triple such that each pair is linked by a special connection. We prove that a chordal graph is a directed path graph if and only if it does not contain a special asteroidal triple. © 2010 Wiley Periodicals, Inc. J Graph Theory 68:103‐112, 2011 相似文献
12.
Louis Ibarra 《Discrete Applied Mathematics》2009,157(8):1737-1749
We present a new representation of a chordal graph called the clique-separator graph, whose nodes are the maximal cliques and minimal vertex separators of the graph. We present structural properties of the clique-separator graph and additional properties when the chordal graph is an interval graph, proper interval graph, or split graph. We also characterize proper interval graphs and split graphs in terms of the clique-separator graph. We present an algorithm that constructs the clique-separator graph of a chordal graph in O(n3) time and of an interval graph in O(n2) time, where n is the number of vertices in the graph. 相似文献
13.
The problem of recognizing cover-incomparability graphs (i.e. the graphs obtained from posets as the edge-union of their covering and incomparability graph) was shown to be NP-complete in general [J. Maxová, P. Pavlíkova, A. Turzík, On the complexity of cover-incomparability graphs of posets, Order 26 (2009) 229-236], while it is for instance clearly polynomial within trees. In this paper we concentrate on (classes of) chordal graphs, and show that any cover-incomparability graph that is a chordal graph is an interval graph. We characterize the posets whose cover-incomparability graph is a block graph, and a split graph, respectively, and also characterize the cover-incomparability graphs among block and split graphs, respectively. The latter characterizations yield linear time algorithms for the recognition of block and split graphs, respectively, that are cover-incomparability graphs. 相似文献
14.
Tnaz Ekim Pavol Hell Juraj Stacho Dominique de Werra 《Discrete Applied Mathematics》2008,156(13):2469-2479
Polar graphs are a common generalization of bipartite, cobipartite, and split graphs. They are defined by the existence of a certain partition of vertices, which is NP-complete to decide for general graphs. It has been recently proved that for cographs, the existence of such a partition can be characterized by finitely many forbidden subgraphs, and hence tested in polynomial time. In this paper we address the question of polarity of chordal graphs, arguing that this is in essence a question of colourability, and hence chordal graphs are a natural restriction. We observe that there is no finite forbidden subgraph characterization of polarity in chordal graphs; nevertheless we present a polynomial time algorithm for polarity of chordal graphs. We focus on a special case of polarity (called monopolarity) which turns out to be the central concept for our algorithms. For the case of monopolar graphs, we illustrate the structure of all minimal obstructions; it turns out that they can all be described by a certain graph grammar, permitting our monopolarity algorithm to be cast as a certifying algorithm. 相似文献
15.
A blocking quadruple (BQ) is a quadruple of vertices of a graph such that any two vertices of the quadruple either miss (have no neighbours on) some path connecting the remaining two vertices of the quadruple, or are connected by some path missed by the remaining two vertices. This is akin to the notion of asteroidal triple used in the classical characterization of interval graphs by Lekkerkerker and Boland [Klee, V., What are the intersection graphs of arcs in a circle?, American Mathematical Monthly 76 (1976), pp. 810–813.].In this note, we first observe that blocking quadruples are obstructions for circular-arc graphs. We then focus on chordal graphs, and study the relationship between the structure of chordal graphs and the presence/absence of blocking quadruples.Our contribution is two-fold. Firstly, we provide a forbidden induced subgraph characterization of chordal graphs without blocking quadruples. In particular, we observe that all the forbidden subgraphs are variants of the subgraphs forbidden for interval graphs [Klee, V., What are the intersection graphs of arcs in a circle?, American Mathematical Monthly 76 (1976), pp. 810–813.]. Secondly, we show that the absence of blocking quadruples is sufficient to guarantee that a chordal graph with no independent set of size five is a circular-arc graph. In our proof we use a novel geometric approach, constructing a circular-arc representation by traversing around a carefully chosen clique tree. 相似文献
16.
Basic chordal graphs arose when comparing clique trees of chordal graphs and compatible trees of dually chordal graphs. They were defined as those chordal graphs whose clique trees are exactly the compatible trees of its clique graph.In this work, we consider some subclasses of basic chordal graphs, like hereditary basic chordal graphs, basic DV and basic RDV graphs, we characterize them and we find some other properties they have, mostly involving clique graphs. 相似文献
17.
René van Bevern Robert Bredereck Laurent Bulteau Jiehua Chen Vincent Froese Rolf Niedermeier Gerhard J. Woeginger 《Journal of Graph Theory》2017,85(2):297-335
The partition of graphs into “nice” subgraphs is a central algorithmic problem with strong ties to matching theory. We study the partitioning of undirected graphs into same‐size stars, a problem known to be NP‐complete even for the case of stars on three vertices. We perform a thorough computational complexity study of the problem on subclasses of perfect graphs and identify several polynomial‐time solvable cases, for example, on interval graphs and bipartite permutation graphs, and also NP‐complete cases, for example, on grid graphs and chordal graphs. 相似文献
18.
Packing a maximum number of disjoint triangles into a given graph G is NP-hard, even for most classes of structured graphs. In contrast, we show that packing a maximum number of independent
(that is, disjoint and nonadjacent) triangles is polynomial-time solvable for many classes of structured graphs, including
weakly chordal graphs, asteroidal triple-free graphs, polygon-circle graphs, and interval-filament graphs. These classes contain
other well-known classes such as chordal graphs, cocomparability graphs, circle graphs, circular-arc graphs, and outerplanar
graphs. Our results apply more generally to independent packings by members of any family of connected graphs.
Research of both authors is supported by the Natural Sciences and Engineering Research Council of Canada. 相似文献
19.
J. Mark Keil 《Discrete Applied Mathematics》2006,154(14):1983-1995
Subtree filament graphs are the intersection graphs of subtree filaments in a tree. This class of graphs contains subtree overlap graphs, interval filament graphs, chordal graphs, circle graphs, circular-arc graphs, cocomparability graphs, and polygon-circle graphs. In this paper we show that, for circle graphs, the clique cover problem is NP-complete and the h-clique cover problem for fixed h is solvable in polynomial time. We then present a general scheme for developing approximation algorithms for subtree filament graphs, and give approximation algorithms developed from the scheme for the following problems which are NP-complete on circle graphs and therefore on subtree filament graphs: clique cover, vertex colouring, maximum k-colourable subgraph, and maximum h-coverable subgraph. 相似文献