共查询到20条相似文献,搜索用时 31 毫秒
1.
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. 相似文献
2.
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. 相似文献
3.
A forced cycle of a graph is a cycle in such that has a unique perfect matching. A graph is a cycle-forced graph if every cycle in is a forced cycle. In this paper, we give a characterization of cycle-forced hamiltonian bipartite graphs. 相似文献
4.
5.
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. 相似文献
6.
7.
The tree-depth of is the smallest value of for which a labeling of the vertices of with elements from exists such that any path joining two vertices with the same label contains a vertex having a higher label. The graph is -critical if it has tree-depth and every proper minor of has smaller tree-depth.Motivated by a conjecture on the maximum degree of -critical graphs, we consider the property of 1-uniqueness, wherein any vertex of a critical graph can be the unique vertex receiving label 1 in an optimal labeling. Contrary to an earlier conjecture, we construct examples of critical graphs that are not 1-unique and show that 1-unique graphs can have arbitrarily many more edges than certain critical spanning subgraphs. We also show that -critical graphs on vertices are 1-unique and use 1-uniqueness to show that the Andrásfai graphs are critical with respect to tree-depth. 相似文献
8.
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. 相似文献
9.
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. 相似文献
10.
Kathie Cameron Murilo V.G. da Silva Shenwei Huang Kristina Vušković 《Discrete Mathematics》2018,341(2):463-473
A graph is even-hole-free if it has no induced even cycles of length 4 or more. A cap is a cycle of length at least 5 with exactly one chord and that chord creates a triangle with the cycle. In this paper, we consider (cap, even hole)-free graphs, and more generally, (cap, 4-hole)-free odd-signable graphs. We give an explicit construction of these graphs. We prove that every such graph has a vertex of degree at most , and hence , where denotes the size of a largest clique in and denotes the chromatic number of . We give an algorithm for -coloring these graphs for fixed and an algorithm for maximum weight stable set, where is the number of vertices and is the number of edges of the input graph. We also give a polynomial-time algorithm for minimum coloring.Our algorithms are based on our results that triangle-free odd-signable graphs have treewidth at most 5 and thus have clique-width at most 48, and that (cap, 4-hole)-free odd-signable graphs without clique cutsets have treewidth at most and clique-width at most 48. 相似文献
11.
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. 相似文献
12.
13.
Michael Gentner Irene Heinrich Simon Jäger Dieter Rautenbach 《Discrete Mathematics》2018,341(1):119-125
A prominent parameter in the context of network analysis, originally proposed by Watts and Strogatz (1998), is the clustering coefficient of a graph . It is defined as the arithmetic mean of the clustering coefficients of its vertices, where the clustering coefficient of a vertex of is the relative density of its neighborhood if is at least , and otherwise. It is unknown which graphs maximize the clustering coefficient among all connected graphs of given order and size.We determine the maximum clustering coefficients among all connected regular graphs of a given order, as well as among all connected subcubic graphs of a given order. In both cases, we characterize all extremal graphs. Furthermore, we determine the maximum increase of the clustering coefficient caused by adding a single edge. 相似文献
14.
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. 相似文献
15.
16.
We study vertex partitions of graphs according to their Colin de Verdiere parameter μ. By a result of Ding et al. [DOSOO] we know that any graph G with admits a vertex partition into two graphs with μ at most . Here we prove that any graph G with admits a vertex partition into three graphs with μ at most . This study is extended to other minor-monotone graph parameters like the Hadwiger number. 相似文献
17.
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. 相似文献
18.
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 . 相似文献
19.
Yehong Shao 《Discrete Mathematics》2018,341(12):3441-3446
Let be a graph and be its line graph. In 1969, Chartrand and Stewart proved that , where and denote the edge connectivity of and respectively. We show a similar relationship holds for the essential edge connectivity of and , written and , respectively. In this note, it is proved that if is not a complete graph and does not have a vertex of degree two, then . An immediate corollary is that for such graphs , where the vertex connectivity of the line graph
and the second iterated line graph are written as and respectively. 相似文献
20.
The acyclic matching number of a graph is the largest size of an acyclic matching in , that is, a matching in such that the subgraph of induced by the vertices incident to edges in is a forest. We show that the acyclic matching number of a connected subcubic graph with edges is at least except for two graphs of order 5 and 6. 相似文献