共查询到20条相似文献,搜索用时 46 毫秒
1.
2.
A graph is minimally -tough if the toughness of is and the deletion of any edge from decreases the toughness. Kriesell conjectured that for every minimally -tough graph the minimum degree . We show that in every minimally -tough graph . We also prove that every minimally -tough, claw-free graph is a cycle. On the other hand, we show that for every positive rational number any graph can be embedded as an induced subgraph into a minimally -tough graph. 相似文献
3.
Let be a finite simple graph. For , the difference of , where is the neighborhood of and is called the critical difference of . is called a critical set if equals the critical difference and is the intersection of all critical sets. is the union of all critical independent sets. An independent set is an inclusion minimal set with if no proper subset of has positive difference.A graph is called a König–Egerváry graph if the sum of its independence number and matching number equals .In this paper, we prove a conjecture which states that for any graph the number of inclusion minimal independent set with is at least the critical difference of the graph.We also give a new short proof of the inequality .A characterization of unicyclic non-König–Egerváry graphs is also presented and a conjecture which states that for such a graph , the critical difference equals , is proved.We also make an observation about using Edmonds–Gallai Structure Theorem as a concluding remark. 相似文献
4.
5.
For a given graph , the -saturation number of a graph is the minimum number of edges in an edge-maximal -free subgraph of . Recently, the -saturation number of the Erd?s–Rényi random graph has been determined asymptotically for any complete graph . In this paper, we give an asymptotic formula for the -saturation number of when is a star graph. 相似文献
6.
Let be a connected graph. A configuration of pebbles on is a function that assigns a nonnegative integer to each vertex. A pebbling move consists of removing two pebbles from one vertex and placing one pebble on an adjacent vertex. A configuration is solvable if after making pebbling moves any vertex can get at least one pebble. The pebbling number of , denoted , is the smallest integer such that any configuration of pebbles on is solvable. A graph has the two-pebbling property if after placing more than pebbles on , where is the number of vertices with pebbles, there is a sequence of pebbling moves so that at least two pebbles can be placed on any vertex. A graph without the two-pebbling property is called a Lemke graph. Previously, an infinite family of Lemke graphs was shown to exist by subdividing edges of the original Lemke graph. In this paper, we introduce a new way to create infinite families of Lemke graphs based on adding vertices as well as subdividing edges. We also characterize the configurations that violate the two-pebbling property on these graphs and conjecture another infinite family of Lemke graphs that generalizes the original Lemke graph. 相似文献
7.
John Asplund Kossi Edoh Ruth Haas Yulia Hristova Beth Novick Brett Werner 《Discrete Mathematics》2018,341(10):2938-2948
For a graph and, the shortest path reconfiguration graph of with respect to and is denoted by . The vertex set of is the set of all shortest paths between and in . Two vertices in are adjacent, if their corresponding paths in differ by exactly one vertex. This paper examines the properties of shortest path graphs. Results include establishing classes of graphs that appear as shortest path graphs, decompositions and sums involving shortest path graphs, and the complete classification of shortest path graphs with girth 5 or greater. We include an infinite family of well structured examples, showing that the shortest path graph of a grid graph is an induced subgraph of a lattice. 相似文献
8.
The vertex arboricity of a graph is the minimum number of colors required to color the vertices of such that no cycle is monochromatic. The list vertex arboricity is the list-coloring version of this concept. In this note, we prove that if is a toroidal graph, then ; and if and only if contains as an induced subgraph. 相似文献
9.
For a given graph G and a positive integer r the r-path graph, , has for vertices the set of all paths of length r in G. Two vertices are adjacent when the intersection of the corresponding paths forms a path of length , and their union forms either a cycle or a path of length in G. Let be the k-iteration of r-path graph operator on a connected graph G. Let H be a subgraph of . The k-history is a subgraph of G that is induced by all edges that take part in the recursive definition of H. We present some general properties of k-histories and give a complete characterization of graphs that are k-histories of vertices of 2-path graph operator. 相似文献
10.
A transition in a graph is defined as a pair of adjacent edges. A transition system of an Eulerian graph refers to a set of partitions such that for each vertex of the graph, there corresponds to a partition of the set of edges incident to the vertex into transitions. A generalized transition system over a graph defines a set of transitions over . A compatible Eulerian circuit of an Eulerian graph with a generalized transition system is defined as an Eulerian circuit in which no two consecutive edges form a transition defined by . In this paper, we further introduce the concept of weakly generalized transition system which is an extension of the generalized transition system and prove some Ore-type sufficient conditions for the existence of compatible Eulerian circuits in Eulerian graphs with (weakly) generalized transition systems and obtain corresponding results for Eulerian digraphs. Our conditions improve some previous results due to Jackson and Isaak, respectively. 相似文献
11.
Let be a graph and let be a group of automorphisms of . The graph is called -normal if is normal in the automorphism group of . Let be a finite non-abelian simple group and let with . In this paper we prove that if every connected pentavalent symmetric -vertex-transitive graph is -normal, then every connected pentavalent symmetric -vertex-transitive graph is -normal. This result, among others, implies that every connected pentavalent symmetric -vertex-transitive graph is -normal except is one of 57 simple groups. Furthermore, every connected pentavalent symmetric -regular graph is -normal except is one of 20 simple groups, and every connected pentavalent -symmetric graph is -normal except is one of 17 simple groups. 相似文献
13.
Akira Kamibeppu 《Discrete Mathematics》2012,312(6):1123-1127
A hole of a graph is an induced cycle of length at least 4. Kim (2005) [3] conjectured that the competition number is bounded by for any graph , where is the number of holes of . Li and Chang (2009) [5] proved that the conjecture is true for a graph whose holes all satisfy a property called ‘independence’. In this paper, by using similar proof techniques in Li and Chang (2009) [5], we prove the conjecture for graphs satisfying two conditions that allow the holes to overlap a lot. 相似文献
14.
15.
Boris Brimkov Jennifer Edmond Robert Lazar Bernard Lidický Kacy Messerschmidt Shanise Walker 《Discrete Mathematics》2017,340(10):2538-2549
An injective coloring of a graph is an assignment of colors to the vertices of so that any two vertices with a common neighbor have distinct colors. A graph is injectively -choosable if for any list assignment , where for all , has an injective -coloring. Injective colorings have applications in the theory of error-correcting codes and are closely related to other notions of colorability. In this paper, we show that subcubic planar graphs with girth at least 6 are injectively 5-choosable. This strengthens the result of Lu?ar, ?krekovski, and Tancer that subcubic planar graphs with girth at least 7 are injectively 5-colorable. Our result also improves several other results in particular cases. 相似文献
16.
A strong edge coloring of a graph is an assignment of colors to the edges of such that two distinct edges are colored differently if their distance is at most two. The strong chromatic index of a graph , denoted by , is the minimum number of colors needed for a strong edge coloring of . A Halin graph is a plane graph constructed from a tree without vertices of degree two by connecting all leaves through a cycle . If a Halin graph is different from a certain necklace and any wheel , , then we prove that . 相似文献
17.
Let be a simple bipartite graph with . We prove that if the minimum degree of satisfies , then is bipanconnected: for every pair of vertices , and for every appropriate integer , there is an -path of length in . 相似文献
18.
19.
20.