共查询到20条相似文献,搜索用时 15 毫秒
1.
Some Results on Planar Graphs of Class 1 总被引:1,自引:0,他引:1
We consider only simple graphs in this paper unless otherwise stated,A plane gragh is a,particular drawing of a planar graph in the Euclidean plane. For a plane graph G, we denote its vertex set, edge set, face set, and maximum degree by V(G), E(G), F(G), and △(G) (or simply 相似文献
2.
关于半传递图的若干新结果 总被引:1,自引:0,他引:1
我们称无向图X为半传递的,如果它的自同构群Aut X在X的顶点集合以及边集合上作用是传递的,但在X的有序的相邻顶点对的集合上作用非传递。本文综述了自1990年以来若干数学家包括作者本人在半传递图方面研究的最新结果,特别地,我们的工到了具有本原自同构群的半传递图,从而肯定地回答了Holton问题,同时还证明了只存在一个4度27阶的半传递图,解决了Holt问题。 相似文献
3.
4.
5.
令G=(V(G),E(G))是一个图,并令9和f是两个定义在V(G)上的整数值函数且对所有的x∈V(G)有g(x)≤f(z)成立.若对G的每一条边e都存在G的一个分数(g,f)-因子G_h使得h(e)=0,其中h是G_h的示性函数,则称G是一个分数(g,f)-消去图,若在G中删去E′■E(G),|E′|=k后,所得图有分数完美匹配,则称G是分数k-边-可消去的。本文给出了图是1-可消去,2-可消去和k-边-可消去的与韧度和孤立韧度相关的充分条件。证明了这些结果在一定意义上是最好可能的. 相似文献
6.
7.
若干笛卡尔积图的邻点可区别E-全染色 总被引:4,自引:2,他引:2
图G(V,E)的k是一个正整数,f是V(G)∪E(G)到{1,2,…,k}的一个映射,如果u,v∈V(G),则f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv),C(u)≠C(v),称f是图G的邻点可区别E-全染色,称最小的数k为图G的邻点可区别E-全色数.得到了Pm×Pn,Pm×Cn,Cm×Cn的邻点可区别E-全色数,其中C(u)={f(u)}∪{f(uv)uv∈E(G)}. 相似文献
8.
We give elementary constructions of two infinite families of Ramanujan graphs of unbounded degree. The first uses the geometry of buildings over finite fields, and the second uses triangulations of modular curves.Mathematics Subject Classiffications (2000). Primary: 05C25; secondary: 05C50, 51E24 相似文献
9.
黄振杰 《数学的实践与认识》2000,30(4)
一个图 G中含有的三个结点的导出连通子图的个数 S3( G)在网络可靠性中起着重要作用 .在同点数同边数图类中具有最大 S3( G)的图称为 3-优图 ,它所代表的网络是点故障概率接近 1时的最可靠网络 .本文在已有的结果上进一步证明补图为 a K3∪ b K2 ∪ K1和 a K3-x的图分别是各自图类中唯一的 3-优图 ;补图为 a K3∪ ( b-1 ) K2 ∪ 2 K1和 ( a-1 ) K3∪ b K2 ∪ P3的图是该图类中仅有的两个 3-优图 . 相似文献
10.
A graph G is perfectly orderable in the sense of Chvátal if there exists a linear order on the set of vertices of G such that no induced path with vertices a, b, c, d and edges ab, bc, cd has a < b and d < c. A perfectly orderable graph G is brittle if every induced subgraph of G contains a vertex which is either endpoint or midpoint of no induced path with three edges in G. We present a new class of brittle graphs by forbidden configurations. 相似文献
11.
设G是n阶连通图.γ_c(G),d_c(G),i(G)和ir(G)分别表示G图的连通Domination数,连通Domatic数,独立Domination数和Irredundance数,k(G)表示G的连通度.本文证明了下列结论. (1) 如n≥3,则i(G) γ_c(G)≤n [n/3]-2; (2) γ_c(G)≤4ir(G)-2; (3) γ_c(G)≤k(G) 1; (4) 如G≠K_n,则d_c(G)≤k(G). 此外,本文给出了满足等式γ_c(G) γ_c(G)=n和γ_c(G) γ_c(G)=n 1的图G的一个特征. 相似文献
12.
The total bondage number b t (G) of a graph G with no isolated vertex is the cardinality of a smallest set of edges ${E^{\prime}\subseteq E(G)}$ for which (1) G?E′ has no isolated vertex, and (2) ${\gamma_{t}(G-E^{\prime})>\gamma_{t}(G)}$ . We improve some results on the total bondage number of a graph and give a constructive characterization of a certain class of trees achieving the upper bound on the total bondage number. 相似文献
13.
An inequality for superharmonic functions on Riemannian manifolds due to S.Y. Cheng and S-T. Yau is adapted to the setting of graphs. A number of corollaries are discussed, including a Harnack inequality for graphs having at most quadratic growth and satisfying a certain connectedness condition. 相似文献
14.
The Ramsey number r(H, K
n
) is the smallest positive integer N such that every graph of order N contains either a copy of H or an independent set of size n. The Turán number ex(m, H) is the maximum number of edges in a graph of order m not containing a copy of H. We prove the following two results: (1) Let H be a graph obtained from a tree F of order t by adding a new vertex w and joining w to each vertex of F by a path of length k such that any two of these paths share only w. Then r(H,Kn) £ ck,t [(n1+1/k)/(ln1/k n)]{r(H,K_n)\leq c_{k,t}\, {n^{1+1/k}\over \ln^{1/k} n}} , where c
k,t
is a constant depending only on k and t. This generalizes some results in Li and Rousseau (J Graph Theory 23:413–420, 1996), Li and Zang (J Combin Optim 7:353–359,
2003), and Sudakov (Electron J Combin 9, N1, 4 pp, 2002). (2) Let H be a bipartite graph with ex(m, H) = O(m
γ
), where 1 < γ < 2. Then r(H,Kn) £ cH ([(n)/(lnn)])1/(2-g){r(H,K_n)\leq c_H ({n\over \ln n})^{1/(2-\gamma)}}, where c
H
is a constant depending only on H. This generalizes a result in Caro et al. (Discrete Math 220:51–56, 2000). 相似文献
16.
Doklady Mathematics - New bounds on the modularity of distance graphs were obtained and the exact value of modularity was calculated for G(n, 2, 1) graphs. 相似文献
17.
Given a graph G and an integer k, a set S of vertices in G is k-sparse if S induces a graph with a maximum degree of at most k. Many parameters in graph theory are defined in terms of independent sets. Accordingly, their definitions can be expanded taking into account the notion of k-sparse sets. In this discussion, we examine several of those extensions. Similarly, S is k-dense if S induces a k-sparse graph in the complement of G. A partition of V(G) is a k-defective cocoloring if each part is k-sparse or k-dense. The minimum order of all k-defective cocolorings is the k-defective cochromatic number of G and denoted z k (G). Analogous notions are defined similarly for k-defective coloring where V(G) is partitioned into k-sparse parts. We show the NP-hardness of computing maximum k-defective sets in planar graphs with maximum degree at most k + 1 and arbitrarily large girth. We explore the extension of Ramsey numbers to k-sparse and k-dense sets of vertices. Lastly, we discuss some bounds related to k-defective colorings and k-defective cocolorings. 相似文献
18.
19.
关于图的若干介值问题 总被引:2,自引:0,他引:2
对连通图G,以C_i(G),■(G)分别表G的有i条边的连通支撑子图之集与连通子图之集,以C~i(G),(?)(G)分别表G的顶点数为i的子树集与连通子图之集.本文讨论了这四类子图簇对若干基本参数及端点数的介值性,从而对已有的一些结果作了若干有意义的拓广. 相似文献
20.
Hua Zhang 《Graphs and Combinatorics》2014,30(5):1319-1324
A graph Γ is called half-arc-transitive if it’s automorphism group Aut Γ is transitive on the vertex set and edge set, but not on the arc set of the graph Γ, and it is called 2-path-transitive if Aut Γ is transitive on the set of the 2-paths. In this paper we construct a class of 2-path-transitive graphs from some symmetric groups, based on which a new class of half-arc-transitive graphs is given. 相似文献