共查询到20条相似文献,搜索用时 234 毫秒
1.
It is known that there exists a cycle through any nine vertices of a 3-connected cubic graphG. Here we show that if an edge is removed from such a graph, then there is still a cycle through any five vertices. Furthermore,
we characterise the circumstances in which there fails to be a cycle through six. As corollaries we are able to prove that
a 3-connected cubic graph has a cycle through any specified five vertices and one edge, and to classify the conditions under
which it has a cycle through four chosen vertices and two edges.
We are able to use the five and six vertex results to show that a 3-connected cubic graph has a cycle which passes through
any ten given vertices if and only if the graph is not contractible to the Petersen graph in such a way that the ten vertices
each map to a distinct vertex of the Petersen graph. 相似文献
2.
Stephen B. Maurer 《Discrete Mathematics》1975,11(2):147-159
An interval in a graph is a subgraph induced by all the vertices on shortest paths between two given vertices. Intervals in matroid basis graphs satisfy many nice properties. Key results are: (1) any two vertices of a basis graph are together in some longest interval; (2) every basis graph with the minimum number of vertices for its diameter is an interval, indeed a hypercube. (1) turns out to be a simple case of a theorem in Edmonds' theory of matroid partition. 相似文献
3.
Broadcasting is the process of information dissemination in a communication network in which a message, originated by one member, is transmitted to all members of the network. A broadcast graph is a graph which permits broadcasting from any originator in minimum time. The broadcast function B(n) is the minimum number of edges in any broadcast graph on n vertices. In this paper, we construct a broadcast graph on 26 vertices with 42 edges to prove B(26) = 42. 相似文献
4.
A. V. Ivashchenko 《Discrete Mathematics》1993,120(1-3):107-114
Every graph can be represented as the intersection graph on a family of closed unit cubes in Euclidean space En. Cube vertices have integer coordinates. The coordinate matrix, A(G)={vnk} of a graph G is defined by the set of cube coordinates. The imbedded dimension of a graph, Bp(G), is a number of columns in matrix A(G) such that each of them has at least two distinct elements vnk≠vpk. We show that Bp(G)=cub(G) for some graphs, and Bp(G)n−2 for any graph G on n vertices. The coordinate matrix uses to obtain the graph U of radius 1 with 3n−2 vertices that contains as an induced subgraph a copy of any graph on n vertices. 相似文献
5.
6.
The eternal domination problem requires a graph to be protected against an infinitely long sequence of attacks on vertices by guards located at vertices, the configuration of guards inducing a dominating set at all times. An attack at a vertex with no guard is defended by sending a guard from a neighboring vertex to the attacked vertex. We allow any number of guards to move to neighboring vertices at the same time in response to an attack. We compare the eternal domination number with the vertex cover number of a graph. One of our main results is that the eternal domination number is less than the vertex cover number of any graph of minimum degree at least two having girth at least nine. 相似文献
7.
Sandra M Hedetniemi Andrzej Proskurowski Maciej M Sysło 《Journal of Combinatorial Theory, Series B》1985,38(2):156-167
A maximal outerplane graph (mop) is a plane embedding of a graph in which all vertices lie on the exterior face, and the addition of an edge between any two vertices would destroy this outerplanarity property. Removing the edges of the exterior face of a mop G results in the interior graph of G. We give a necessary and sufficient condition for a graph to be the interior graph of some mop. 相似文献
8.
Seungsang Oh 《Discrete Mathematics》2017,340(12):2762-2768
An independent vertex set of a graph is a set of vertices of the graph in which no two vertices are adjacent, and a maximal independent set is one that is not a proper subset of any other independent set. In this paper we count the number of maximal independent sets of vertices on a complete rectangular grid graph. More precisely, we provide a recursive matrix-relation producing the partition function with respect to the number of vertices. The asymptotic behavior of the maximal hard square entropy constant is also provided. We adapt the state matrix recursion algorithm, recently invented by the author to answer various two-dimensional regular lattice model problems in enumerative combinatorics and statistical mechanics. 相似文献
9.
A topological graph is a graph drawn in the plane so that
its vertices are represented by points, and its edges are
represented by Jordan curves connecting the corresponding points,
with the property that any two curves have at most one point in common.
We define two canonical classes of topological complete
graphs, and prove that every topological complete graph with
n vertices has a canonical subgraph of size at least clog1/8
n,
which belongs to one of these classes. We also show
that every complete topological graph with n
vertices has a non-crossing subgraph isomorphic to any fixed
tree with at most clog1/6
n vertices. 相似文献
10.
The center of a graph is the set of vertices with minimum eccentricity. Graphs in which all vertices are central are called
self-centered graphs. In this paper almost self-centered (ASC) graphs are introduced as the graphs with exactly two non-central
vertices. The block structure of these graphs is described and constructions for generating such graphs are proposed. Embeddings
of arbitrary graphs into ASC graphs are studied. In particular it is shown that any graph can be embedded into an ASC graph
of prescribed radius. Embeddings into ASC graphs of radius two are studied in more detail. ASC index of a graph G is introduced as the smallest number of vertices needed to add to G such that G is an induced subgraph of an ASC graph. 相似文献
11.
A graph is vertex-transitive if its automorphism group acts transitively on vertices of the graph. A vertex-transitive graph is a Cayley graph if its automorphism group contains a subgroup acting regularly on its vertices. In this paper, a complete classification is given of tetravalent vertex-transitive non-Cayley graphs of order \(2p^2\) for any prime p. 相似文献
12.
曲面S的一个极小禁用子图是这样的一个图,它的任何一个顶点的度都不小于3,它不能嵌入在S上,但是删去任何一条边后得到的图能嵌入在S上.本文给出了四种构造一个不可定向曲面的极小禁用子图的方式,即粘合一个顶点,一个图的边被其它的图替换,粘合两个顶点,将一个图放在另一个图的一个曲面嵌入的面内. 相似文献
13.
图G的Wiener指数是指图G中所有顶点对间的距离之和,即W(G)=∑dc(u,u),{u,u}CG其中de(u,u)表示G中顶点u,u之间的距离.三圈图是指边数与顶点数之差等于2的连通图,任意两个圈至多只有一个公共点的三圈图记为T_n~3.研究了三圈图T_n~3的Wiener指数,给出了其具有最小、次小Wiener指数的图结构. 相似文献
14.
Emily Sergel Peter Richter Anh Tran Patrick Curran Jobby Jacob Darren A. Narayan 《Aequationes Mathematicae》2011,82(1-2):65-79
A ranking on a graph is an assignment of positive integers to its vertices such that any path between two vertices of the same rank contains a vertex of strictly larger rank. The rank number of a graph is the fewest number of labels that can be used in a ranking. In this paper we determine rank numbers for some trees and unicyclic graphs. 相似文献
15.
6连通图中的可收缩边 总被引:4,自引:0,他引:4
Kriesell(2001年)猜想:如果κ连通图中任意两个相邻顶点的度的和至少是2[5κ/4]-1则图中有κ-可收缩边.本文证明每一个收缩临界6连通图中有两个相邻的度为6的顶点,由此推出该猜想对κ=6成立。 相似文献
16.
Surya Sekhar Bose Milan Nath Somnath Paul 《Linear algebra and its applications》2012,437(9):2128-2141
A cactus is a connected graph in which any two cycles have at most one common vertex. In this article, we determine the unique graph with minimal distance spectral radius in the class of all cacti with n vertices and k cycles. Also, we determine the unique graph with minimal distance spectral radius in the class of all cacti with n vertices and r pendent vertices. Moreover, we determine the class of cacti in which the maximal distance spectral radius among all cacti with n vertices and k cycles is attained. 相似文献
17.
Ryan Hayward 《Journal of Graph Theory》1996,21(1):67-69
We show that a graph is weakly triangulated, or weakly chordal, if and only if it can be generated by starting with a graph with no edges, and repeatedly adding an edge, so that the new edge is not the middle edge of any chordless path with four vertices. This is a corollary of results due to Sritharan and Spinrad, and Hayward, Hoång and Maffray, and a natural analog of a theorem due to Fulkerson and Gross, which states that a graph is triangulated, or chordal, if and only if it can be generated by starting with a graph with no vertices, and repeatedly adding a vertex, so that the new vertex is not the middle vertex of any chordless path with three vertices. Our result answers the question of whether there exists a composition scheme that generates exactly the class of weakly triangulated graphs. © 1996 John Wiley & Sons, Inc. 相似文献
18.
A.K. Dewdney 《Discrete Mathematics》1973,4(2):139-149
Wagner's theorem (any two maximal plane graphs having p vertices are equivalent under diagonal transformations) is extended to maximal torus graphs, graphs embedded in the torus with a maximal set of edges present. Thus any maximal torus graph having p vertices may be diagonally transformed into any other maximal torus graph having p vertices. As with Wagner's theorem, a normal form representing an intermediate stage in the above transformation is displayed. This result, along with Wagner's theorem, may make possible constructive characterizations of planar and toroidal graphs, through a wholly combinatorial definition of diagonal transformation. 相似文献
19.
20.
D. S. Krotov 《Journal of Applied and Industrial Mathematics》2011,5(2):240-246
A graph of order n ≥ 4 is called switching separable if its modulo-2 sum with some complete bipartite graph on the same set of vertices is divided into two mutually independent
subgraphs, each having at least two vertices. We prove the following: If removing any one or two vertices of a graph always
results in a switching separable subgraph then the graph itself is switching separable. On the other hand, for each odd order
greater than 4, there is a graph that is not switching separable, but removing a vertex always results in a switching separable
subgraph. We show some connection with similar facts on the separability of Boolean functions and the reducibility of n-ary quasigroups. 相似文献