共查询到20条相似文献,搜索用时 812 毫秒
1.
2.
3.
4.
嵌入的联树模型是研究图的曲面嵌入的一种有效方法,尤其能方便快捷地研究图在球面,环面,射影平面,Klein瓶上的嵌入。此方法通过合理选择生成树,得到联树和关联曲面,然后对关联曲面进行计数,计算出图在曲面上的嵌入个数.本文利用嵌入的联树模型得出了循环图C(2n+1,2)(n>2)在射影平面上的嵌入个数. 相似文献
5.
6.
7.
设$\phi: G\rightarrow S$是图$G$在曲面$S$上的2 -胞腔嵌入. 若$G$的所有面都是依次相邻, 即嵌入图$G$的对偶图有哈密顿圈, 则将$\phi$称为一个面依次相邻的嵌入. 该文研究了在克莱茵瓶上有面依次相邻嵌入的图的最大亏格. 相似文献
8.
研究了不可定向曲面上最大亏格嵌入的估计数,得到了几类图的指数级不可定向最大亏格嵌入的估计数的下界.利用电流图理论,证明了完全图K_(12s)在不可定向曲面上至少有2~(3s-1)个最小亏格嵌入;完全图K_(12s+3)在不可定向曲面上至少有2~(2s)个最小亏格嵌入;完全图K_(12s+7)在不可定向曲面上至少有2~(2s+1)个最小亏格嵌入. 相似文献
9.
不依赖图的其它参数, 而主要依据图嵌入在定向曲面上的有关嵌入性质, 该文研究图的最大亏格. 相似文献
10.
图在曲面上嵌入的分类就是确定图在同一曲面上(不等价的)嵌入的数目.本文,利用刘彦佩提出的嵌入的联树模型,得到了双极图与扇图的关联曲面之间的关系,进而由已知结论的双极图的亏格分布和完全亏格分布推导出扇图的亏格分布和完全亏格分布,并给出了扇图在亏格为1-4的不可定向曲面上嵌入的个数的显式. 相似文献
11.
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. 相似文献
12.
Asahi Takaoka 《Discrete Mathematics》2018,341(12):3281-3287
Consider two horizontal lines in the plane. A point on the top line and an interval on the bottom line define a triangle between two lines. The intersection graph of such triangles is called a simple-triangle graph. This paper shows a vertex ordering characterization of simple-triangle graphs as follows: a graph is a simple-triangle graph if and only if there is a linear ordering of the vertices that contains both an alternating orientation of the graph and a transitive orientation of the complement of the graph. 相似文献
13.
图的强符号全控制数有着许多重要的应用背景,因而确定其下界有重要的意义.本文提出了图的强符号全控制数的概念,在构造适当点集的基础上对其进行了研究,给出了:(1)一般图的强符号全控制数的5个独立可达的下界及达到其界值的图;(2)确定了圈、轮图、完全图、完全二部图的强符号全控制数的值. 相似文献
14.
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 相似文献
15.
Fiber-complemented graphs form a vast non-bipartite generalization of median graphs. Using a certain natural coloring of edges, induced by parallelism relation between prefibers of a fiber-complemented graph, we introduce the crossing graph of a fiber-complemented graph G as the graph whose vertices are colors, and two colors are adjacent if they cross on some induced 4-cycle in G. We show that a fiber-complemented graph is 2-connected if and only if its crossing graph is connected. We characterize those fiber-complemented graphs whose crossing graph is complete, and also those whose crossing graph is chordal. 相似文献
16.
17.
Fiber-complemented graphs form a vast non bipartite generalization of median graphs. Using a certain natural coloring of edges, induced by parallelism relation between prefibers of a fiber-complemented graph, we introduce the crossing graph of a fiber-complemented graph G as the graph whose vertices are colors, and two colors are adjacent if they cross on some induced 4-cycle in G. We show that a fiber-complemented graph is 2-connected if and only if its crossing graph is connected. We characterize those fiber-complemented graphs whose crossing graph is complete, and also those whose crossing graph is chordal. 相似文献
18.
We investigate minimal solutions of the Allen–Cahn equation on a Gromov-hyperbolic graph. Under some natural conditions on the graph, we show the existence of non-constant uniformly-bounded minimal solutions with prescribed asymptotic behaviours. For a phase field model on a hyperbolic graph, such solutions describe energy-minimising steady-state phase transitions that converge towards prescribed phases given by the asymptotic directions on the graph. 相似文献
19.
如果图G可以嵌入在平面上,使得每条边最多被交叉1次,则称其为1-可平面图,该平面嵌入称为1-平面图.由于1-平面图G中的交叉点是图G的某两条边交叉产生的,故图G中的每个交叉点c都可以与图G中的四个顶点(即产生c的两条交叉边所关联的四个顶点)所构成的点集建立对应关系,称这个对应关系为θ.对于1-平面图G中任何两个不同的交叉点c_1与c_2(如果存在的话),如果|θ(c_1)∩θ(c_2)|≤1,则称图G是NIC-平面图;如果|θ(c_1)∩θ(c_2)|=0,即θ(c_1)∩θ(c_2)=?,则称图G是IC-平面图.如果图G可以嵌入在平面上,使得其所有顶点都分布在图G的外部面上,并且每条边最多被交叉一次,则称图G为外1-可平面图.满足上述条件的外1-可平面图的平面嵌入称为外1-平面图.现主要介绍关于以上四类图在染色方面的结果. 相似文献
20.
Chao Yang 《Discrete Mathematics》2011,311(14):1290
Sliding puzzles on graphs are generalizations of the Fifteen Puzzle. Wilson has shown that the sliding puzzle on a 2-connected graph always generates all even permutations of the tiles on the vertices of the graph, unless the graph is isomorphic to a cycle or the graph θ0 [R.M. Wilson, Graph puzzles, homotopy, and the alternating group, J. Combin. Theory Ser. B 16 (1974) 86–96]. In a rotating puzzle on a graph, tiles are allowed to be rotated on some of the cycles of the graph. It was shown by Scherphuis that all even permutations of the tiles are also obtainable for the rotating puzzle on a 2-edge-connected graph, except for a few cases. In this paper, Scherphuis’ Theorem is generalized to every connected graph, and Wilson’s Theorem is derived from the generalized Scherphuis’ Theorem, which will give a uniform treatise for these two families of puzzles and reveal the structural relation of the graphs of the two puzzles. 相似文献