共查询到20条相似文献,搜索用时 406 毫秒
1.
David S. Herscovici Benjamin D. Hester Glenn H. Hurlbert 《Discrete Mathematics》2012,312(15):2286-2293
We investigate generalizations of pebbling numbers and of Graham’s pebbling conjecture that , where is the pebbling number of the graph . We develop new machinery to attack the conjecture, which is now twenty years old. We show that certain conjectures imply others that initially appear stronger. We also find counterexamples that shows that Sjöstrand’s theorem on cover pebbling does not apply if we allow the cost of transferring a pebble from one vertex to an adjacent vertex to depend on the weight of the edge and we describe an alternate pebbling number for which Graham’s conjecture is demonstrably false. 相似文献
2.
3.
《Discrete Mathematics》2019,342(3):777-783
Let be a connected graph. A configuration of pebbles assigns a nonnegative integer number of pebbles to each vertex of . A move consists of removing two pebbles from one vertex and placing one pebble on an adjacent vertex. A configuration is solvable if any vertex can get at least one pebble through a sequence of moves. 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 moves so that at least two pebbles can be placed on any vertex. A graph has the odd-two-pebbling property if after placing more than pebbles on , where is the number of vertices with an odd number of pebbles, there is a sequence of moves so that at least two pebbles can be placed on any vertex. In this paper, we prove that the two-pebbling and odd-two-pebbling properties are not equivalent. 相似文献
4.
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. 相似文献
5.
Andrzej Grzesik 《Discrete Mathematics》2012,312(23):3467-3472
We study a graph coloring game in which two players collectively color the vertices of a graph in the following way. In each round the first player (Ann) selects a vertex, and then the second player (Ben) colors it properly, using a fixed set of colors. The goal of Ann is to achieve a proper coloring of the whole graph, while Ben is trying to prevent realization of this project. The smallest number of colors necessary for Ann to win the game on a graph (regardless of Ben’s strategy) is called the indicated chromatic number of , and denoted by . We approach the question how much differs from the usual chromatic number . In particular, whether there is a function such that for every graph . We prove that cannot be linear with leading coefficient less than . On the other hand, we show that the indicated chromatic number of random graphs is bounded roughly by . We also exhibit several classes of graphs for which and show that this equality for any class of perfect graphs implies Clique-Pair Conjecture for this class of graphs. 相似文献
6.
Let be a graph. A set is a restrained dominating set if every vertex not in is adjacent to a vertex in and to a vertex in . The restrained domination number of , denoted by , is the smallest cardinality of a restrained dominating set of . We define the restrained bondage number of a nonempty graph to be the minimum cardinality among all sets of edges for which . Sharp bounds are obtained for , and exact values are determined for several classes of graphs. Also, we show that the decision problem for is NP-complete even for bipartite graphs. 相似文献
7.
8.
For a graph let , and denote its independence number, matching number, and vertex cover number, respectively. If or, equivalently, , then is a König–Egerváry graph.In this paper we give a new characterization of König–Egerváry graphs. 相似文献
9.
Bao-Xuan Zhu 《Discrete Mathematics》2018,341(8):2359-2365
Given two graphs and , assume that and is a subset of . We introduce a new graph operation called the incidence product, denoted by , as follows: insert a new vertex into each edge of , then join with edges those pairs of new vertices on adjacent edges of . Finally, for every vertex , replace it by a copy of the graph
and join every new vertex being adjacent to to every vertex of . It generalizes the line graph operation. We prove that the independence polynomial where is its matching polynomial. Based on this formula, we show that the incidence product of some graphs preserves symmetry, unimodality, reality of zeros of independence polynomials. As applications, we obtain some graphs so-formed having symmetric and unimodal independence polynomials. In particular, the graph introduced by Cvetkovi?, Doob and Sachs has a symmetric and unimodal independence polynomial. 相似文献
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.
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. 相似文献
12.
Let and be the domination number and the game domination number of a graph , respectively. In this paper -maximal graphs are introduced as the graphs for which holds. Large families of -maximal graphs are constructed among the graphs in which their sets of support vertices are minimum dominating sets. -maximal graphs are also characterized among the starlike trees, that is, trees which have exactly one vertex of degree at least . 相似文献
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.
15.
Given a graph , a set is a dominating set of if every vertex of is either in or adjacent to a vertex in . The domination number of , denoted , is the minimum cardinality of a dominating set of . Vizing’s conjecture states that for any graphs and where denotes the Cartesian product of and . In this paper, we continue the work by Anderson et al. (2016) by studying the domination number of the hierarchical product. Specifically, we show that partitioning the vertex set of a graph in a particular way shows a trend in the lower bound of the domination number of the product, providing further evidence that the conjecture is true. 相似文献
16.
Let be a simple connected graph and . An edge set is an -restricted edge cut if is disconnected and each component of contains at least vertices. Let be the minimum size of all -restricted edge cuts and , where is the set of edges with exactly one end vertex in and is the subgraph of induced by . A graph is optimal- if . An optimal- graph is called super -restricted edge-connected if every minimum -restricted edge cut is for some vertex set with and being connected. In this note, we give a characterization of super 2-restricted edge-connected vertex transitive graphs and obtain a sharp sufficient condition for an optimal- vertex transitive graph to be super 3-restricted edge-connected. In particular, a complete characterization for an optimal- minimal Cayley graph to be super 2-restricted edge-connected is obtained. 相似文献
17.
18.
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. 相似文献
19.
In this paper, we study a new coloring parameter of graphs called the gap vertex-distinguishing edge coloring. It consists in an edge-coloring of a graph which induces a vertex distinguishing labeling of such that the label of each vertex is given by the difference between the highest and the lowest colors of its adjacent edges. The minimum number of colors required for a gap vertex-distinguishing edge coloring of is called the gap chromatic number of and is denoted by .We here study the gap chromatic number for a large set of graphs of order and prove that . 相似文献