共查询到20条相似文献,搜索用时 15 毫秒
1.
关于联图P_1VP_n的k-强优美性 总被引:1,自引:0,他引:1
本文研究了联图P_1VP_n的k-强优美性问题.利用K-强优美图的定义,获得了联图P_1VP_n是k-强优美图的必要条件,还得到了当n:2k-1时联图P_1VP_n是k-强优美图,亦是k-优美图,及当n≥3时联图P_1VP_n是2-强优美图,也是2-优美图的结果,推广了联图P_1VP_n是优美图的结果. 相似文献
2.
Lingsheng Shi 《Linear algebra and its applications》2007,422(1):58-66
The spectral radius of a (directed) graph is the largest eigenvalue of adjacency matrix of the (directed) graph. We give the relation on the characteristic polynomials of a directed graph and its line graph, and obtain sharp bounds on the spectral radius of directed graphs. We also give the relation on the spectral radii of a graph and its line graph. As a consequence, the spectral radius of a connected graph does not exceed that of its line graph except that the graph is a path. 相似文献
3.
4.
5.
双随机矩阵有许多重要的应用, 紧图族可以看作是组合矩阵论中关于双随机矩阵的著名的Birkhoff定理的拓广,具有重要的研究价值. 确定一个图是否紧图是个困难的问题,目前已知的紧图族尚且不多.给出了两个重要结果:任意紧图与任意多个孤立点的不交并是紧图;任意紧图的每一个顶点上各增加一条悬挂边的图是紧图. 利用这两个结果,从已知紧图可构造出无穷多个紧图族. 相似文献
6.
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. 相似文献
7.
Anna de Mier 《Discrete Mathematics》2005,301(1):57-65
We prove that if a graph H has the same Tutte polynomial as the line graph of a d-regular, d-edge-connected graph, then H is the line graph of a d-regular graph. Using this result, we prove that the line graph of a regular complete t-partite graph is uniquely determined by its Tutte polynomial. We prove the same result for the line graph of any complete bipartite graph. 相似文献
8.
刘彦佩教授给出了平面图的辅助图.推广平面图的辅助图到射影平面,给出标号图的射影平面性的如下刻画:给定标号图$G$对应的辅助图是平衡的当且仅当$G$是射影平面图. 相似文献
9.
The authors introduce a notion of a weak graph map homotopy (they call it
M-homotopy), discuss its properties and applications. They prove that the weak graph
map homotopy equivalence between graphs coincides with the graph homotopy equivalence
defined by Yau et al in 2001. The difference between them is that the weak graph map
homotopy transformation is defined in terms of maps, while the graph homotopy transformation is defined by means of combinatorial operations. They discuss its advantages over
the graph homotopy transformation. As its applications, they investigate the mapping
class group of a graph and the 1-order MP-homotopy group of a pointed simple graph.
Moreover, they show that the 1-order MP-homotopy group of a pointed simple graph is
invariant up to the weak graph map homotopy equivalence. 相似文献
10.
11.
12.
A permutation graph over a graph was introduced by Lee and Sohn in [8] as a generalization of both a graph bundle over a
graph and a standard permutation graph, and they gave a characterization of a natural isomorphism and an automorphism of a
given permutation graph over a graph. In this paper, we enumerate the natural isomorphism classes of cycle permutation graphs
over a graph.
Received: October 21, 1996 Revised: August 25, 1997 相似文献
13.
针对简单图G与Mycielski's图之间的关系,讨论了路、圈、星、扇、轮和完全图的Mycielski's图的邻点可区别E-全染色,给出了路、圈、星、扇、轮和完全图的Mycielski's图的邻点可区别E-全色数. 相似文献
14.
(下整)和标号与排斥(下整)和标号是图的一种压缩表示.一个图G称为下整和图,若它同构于某个S Q+的下整和图.图Pn×K2称为梯子.本文给出了梯子细分图Ln*的定义,并确定了梯子细分图Ln*的排斥(下整)和数. 相似文献
15.
(下整)和标号与排斥(下整)和标号是图的一种压缩表示.一个图G称为下整和图,若它同构于某个SQ+的下整和图.图Pn×K2称为梯子.本文给出了梯子细分图Ln*的定义,并确定了梯子细分图Ln*的排斥(下整)和数. 相似文献
16.
扈生彪 《数学的实践与认识》2003,33(10):85-87
记 Gr为任意图 G的 r个拷贝中的对应点 ( r个 )分别与星图 Sr+ 1 的 r个 1度点粘接后得到的图 ,又记 H r为该图 G的相应点与星图 Sr+ 1 的 r度点粘接后得到的图 .如果 G不含三角形 ,则图 ( r- 1) K1 ∪ Gr和图 ( r- 1) G∪ H r伴随等价 ,进而它们的补图色等价 相似文献
17.
Dehmer and Mowshowitz introduced a class of generalized graph entropies using known information‐theoretic measures. These measures rely on assigning a probability distribution to a graph. In this article, we prove some extremal properties of such generalized graph entropies by using the graph energy and the spectral moments. Moreover, we study the relationships between the generalized graph entropies and compute the values of the generalized graph entropies for special graph classes. © 2014 Wiley Periodicals, Inc. Complexity 21: 35–41, 2015 相似文献
18.
20.
This paper deals with a problem to decide whether a given graph structure appears as a pattern in the structure of a given graph. A graph pattern is a connected graph with structured variables. A variable is an ordered list of vertices that can be replaced with a connected graph by a kind of hyperedge replacements. The graph pattern matching problem (GPMP) is the computational problem to decide whether a given graph pattern matches a given graph. In this paper, we show that GPMP is solvable in polynomial time if for a given graph pattern p, the lengths of all variables of p are 2 and the base graph of p is of bounded treewidth. 相似文献