共查询到20条相似文献,搜索用时 546 毫秒
1.
无自圈的极小2-棱-连通图构造已由[1]及[3]给出,最近朱必文又得到了临界2-棱-连通图的构造本文研究了极小2-棱-连通图与临界2-棱-连通图之间的转化关系,从而得到了由前者过渡到后者的一种方法。本文在极小2-棱-连通图构造的基础上首先研究了临界-极小2-棱-连通图的构造,由此得出临界2-棱-连通图的一种非常简洁的递归结 相似文献
2.
最大临界2-边连通图的结构 总被引:3,自引:0,他引:3
丁颂康 《数学年刊A辑(中文版)》1985,(4)
假若G是一个2-边连通图,但对G中任一点v,G\{v}不是2-边连通图,则称G为一个临界2-边连通图。具有最大边数的临界2-边连通图称为一个最大临界图。文[1]中,作者给出了p阶临界2-边连通图的边数的最大界f(p),列出了最大临界图结构的不同情况。并且他们猜测已经找出所有这类图。本文将证明他们的猜想是正确的。 相似文献
3.
4.
5.
6.
M.Kriesell证明了收缩临界5-连通图的平均度不超过24并猜想收缩临界5-连通图的平均度小于10.本文构造了一个反例证明M.Kriesell的猜想不成立并给出了收缩临界5-连通图平均度新的上界. 相似文献
7.
G是3-连通图,e是G中的一条边.若G-e是3-连通图的一个剖分,则称e是3-连通图的可去边.否则,e是G中不可去边.本给出3-连通3-正则图中生成树外可去边的分布情况及数目. 相似文献
8.
9.
图的最小特征值定义为图的邻接矩阵的最小特征值,是刻画图结构性质的一个重要代数参数. 在所有给定阶数的补图为2-点或2-边连通的图中, 刻画了最小特征值达到极小的唯一图, 并给出了这类图最小特征值的下界. 相似文献
10.
p阶临界2-边连通图的最大边数 总被引:2,自引:0,他引:2
设G=(V,E)是2-边连通图,若对每个点v∈V,G-v不是2-边连通图,则称G是临界2-边连通图. 本文证明了p阶临界2-边连通图的最大边数是 7, P=6; (1/8)(P~2+4p) p=0(mod 4); f(p)= (1/8)(P~2+2p+13) p=1(mod 4); (1/8)(P~2+28) p=(2mod 4),p≠6 (1/8)(P~2+2p+9) p=3(mod 4)。并且给出了达到最大边数的极值图. 相似文献
11.
具有割点的标号Euler图的计数 总被引:1,自引:0,他引:1
本文讲座了具有k(k≥2)个割点,并且所有割点均分布在一个2-连能Euler图的标号Euler图的计数,在这里给出了有含有n个2-连能Euler图和k(k≥2)个割点,并且所有割点均分布在其中一2-连能Euler图的标号Euler图的指数型生成函数。 相似文献
12.
Anna Adamaszek Michal Adamaszek Matthias Mnich Jens M. Schmidt 《Graphs and Combinatorics》2016,32(5):1641-1650
We propose a conjecture regarding the lower bound for the number of edges in locally k-connected graphs and we prove it for \(k=2\). In particular, we show that every connected locally 2-connected graph is \(M_3\)-rigid. For the special case of surface triangulations, this fact was known before using topological methods. We generalize this result to all locally 2-connected graphs and give a purely combinatorial proof. Our motivation to study locally k-connected graphs comes from lower bound conjectures for flag triangulations of manifolds, and we discuss some more specific problems in this direction. 相似文献
13.
Broersma and Veldman proved that every 2-connected claw-free and P 6-free graph is hamiltonian. Chen et al. extended this result by proving every 2-connected claw-heavy and P 6-free graph is hamiltonian. On the other hand, Li et al. constructed a class of 2-connected graphs which are claw-heavy and P 6-o-heavy but not hamiltonian. In this paper, we further give some Ore-type degree conditions restricting to induced copies of P 6 of a 2-connected claw-heavy graph that can guarantee the graph to be hamiltonian. This improves some previous related results. 相似文献
14.
A.A. El-Atik H.M. Abu Donia A.S. Salama 《Journal of the Egyptian Mathematical Society》2013,21(1):63-67
In this paper, by using b-open (=γ-open) sets we study the concept of b-separated sets. With this concept we study the notion of b-connected sets and strongly b-connected sets. We give some properties of such concepts with some b-separation axioms and compact spaces. Finally, we construct a new topological space on a connected graph. 相似文献
15.
强嵌入猜想称:任意2-连通图都可以强嵌入到某一曲面上.本文通过分析极大外平面图的结构以及强嵌入的特征,讨论了该图类的不可定向强最大亏格,并给出了一个复杂度为O(nlogn)的算法.其中部分图类的强最大亏格嵌入提供该图的一个少双圈覆盖. 相似文献
16.
《Discrete Mathematics》2023,346(2):113249
Barnette's Conjecture claims that all cubic, 3-connected, planar, bipartite graphs are Hamiltonian. We give a translation of this conjecture into the matching-theoretic setting. This allows us to relax the requirement of planarity to give the equivalent conjecture that all cubic, 3-connected, Pfaffian, bipartite graphs are Hamiltonian.A graph, other than the path of length three, is a brace if it is bipartite and any two disjoint edges are part of a perfect matching. Our perspective allows us to observe that Barnette's Conjecture can be reduced to cubic, planar braces. We show a similar reduction to braces for cubic, 3-connected, bipartite graphs regarding four stronger versions of Hamiltonicity. Note that in these cases we do not need planarity.As a practical application of these results, we provide some supplements to a generation procedure for cubic, 3-connected, planar, bipartite graphs discovered by Holton et al. (1985) [14]. These allow us to check whether a graph we generated is a brace. 相似文献
17.
In 1966, Barnette introduced a set of graphs, called circuit graphs, which are obtained from 3-connected planar graphs by deleting a vertex. Circuit graphs and 3-connected planar graphs share many interesting properties which are not satisfied by general 2-connected planar graphs. Circuit graphs have nice closure properties which make them easier to deal with than 3-connected planar graphs for studying some graph-theoretic properties. In this paper, we study some enumerative properties of circuit graphs. For enumeration purpose, we define rooted circuit maps and compare the number of rooted circuit maps with those of rooted 2-connected planar maps and rooted 3-connected planar maps. 相似文献
18.
Whitney’s 2-switching theorem states that any two embeddings of a 2-connected planar graph in S 2 can be connected via a sequence of simple operations, named 2-switching. In this paper, we obtain two operations on planar graphs from the view point of knot theory, which we will term “twisting” and “2-switching” respectively. With the twisting operation, we give a pure geometrical proof of Whitney’s 2-switching theorem. As an application, we obtain some relationships between two knots which correspond to the same signed planar graph. Besides, we also give a necessary and sufficient condition to test whether a pair of reduced alternating diagrams are mutants of each other by their signed planar graphs. 相似文献
19.
A result of Korte and Lovász states that the basis graph of every 2- connected greedoid is connected. We prove that the basis graph of every 3-connected branching greedoid is (δ -- 1)-connected, where δ is the minimum in-degree (disregarding the root) of the underlying rooted directed (multi) graph. We also give examples showing that this results is (in some sense) best possible. 相似文献
20.
《Discrete Mathematics》2020,343(7):111904
An even cycle decomposition of a graph is a partition of its edges into cycles of even length. In 2012, Markström conjectured that the line graph of every 2-connected cubic graph has an even cycle decomposition and proved this conjecture for cubic graphs with oddness at most 2. However, for 2-connected cubic graphs with oddness 2, Markström only considered these graphs with a chordless 2-factor. (A chordless 2-factor of a graph is a 2-factor consisting of only induced cycles.) In this paper, we first construct an infinite family of 2-connected cubic graphs with oddness 2 and without chordless 2-factors. We then give a complete proof of Markström’s result and further prove this conjecture for cubic graphs with oddness 4. 相似文献