共查询到20条相似文献,搜索用时 31 毫秒
1.
2.
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. 相似文献
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.
6.
7.
8.
9.
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 . 相似文献
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.
Jakub Przybyło 《Discrete Mathematics》2017,340(10):2402-2407
Consider a positive integer and a graph with maximum degree and without isolated edges. The least so that a proper edge colouring exists such that for every pair of distinct vertices at distance at most in is denoted by . For , it has been proved that . For any in turn an infinite family of graphs is known with . We prove that, on the other hand, for . In particular, we show that if . 相似文献
12.
Zoltán Lóránt Nagy 《Discrete Mathematics》2018,341(4):1078-1083
Let be an arbitrary finite projective plane of order . A subset of its points is called saturating if any point outside is collinear with a pair of points from . Applying probabilistic tools we improve the upper bound on the smallest possible size of the saturating set to . The same result is presented using an algorithmic approach as well, which points out the connection with the transversal number of uniform multiple intersecting hypergraphs. 相似文献
13.
A star edge-coloring of a graph is a proper edge coloring such that every 2-colored connected subgraph of is a path of length at most 3. For a graph , let the list star chromatic index of , , be the minimum such that for any -uniform list assignment for the set of edges, has a star edge-coloring from . Dvo?ák et al. (2013) asked whether the list star chromatic index of every subcubic graph is at most 7. In Kerdjoudj et al. (2017) we proved that it is at most 8. In this paper we consider graphs with any maximum degree, we proved that if the maximum average degree of a graph is less than (resp. 3), then (resp. ). 相似文献
14.
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 . 相似文献
15.
16.
For a set of vertices of a graph , a vertex in , and a vertex in , let be the distance of and in the graph . Dankelmann et al. (2009) define to be an exponential dominating set of if for every vertex in , where . Inspired by this notion, we define to be an exponential independent set of if for every vertex in , and the exponential independence number of as the maximum order of an exponential independent set of .Similarly as for exponential domination, the non-local nature of exponential independence leads to many interesting effects and challenges. Our results comprise exact values for special graphs as well as tight bounds and the corresponding extremal graphs. Furthermore, we characterize all graphs for which equals the independence number for every induced subgraph of , and we give an explicit characterization of all trees with . 相似文献
17.
For every , we present a set of points in the plane such that every planar 3-tree with n vertices has a straight-line embedding in the plane in which the vertices are mapped to a subset of . This is the first subquadratic upper bound on the cardinality of universal point sets for planar 3-trees, as well as for the class of 2-trees and serial parallel graphs. 相似文献
18.
We study strong graph bundles : a concept imported from topology which generalizes both covering graphs and product graphs. Roughly speaking, a strong graph bundle always involves three graphs , and and a projection with fiber (i.e. for all ) such that the preimage of any edge of is trivial (i.e. ). Here we develop a framework to study which subgraphs of have trivial preimages (i.e. ) and this allows us to compare and classify several variations of the concept of strong graph bundle. As an application, we show that the clique operator preserves triangular graph bundles (strong graph bundles where preimages of triangles are trivial) thus yielding a new technique for the study of clique divergence of graphs. 相似文献
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.
In Mader (2010), Mader conjectured that for every positive integer and every finite tree with order , every -connected, finite graph with contains a subtree isomorphic to such that is -connected. In the same paper, Mader proved that the conjecture is true when is a path. Diwan and Tholiya (2009) verified the conjecture when . In this paper, we will prove that Mader’s conjecture is true when is a star or double-star and . 相似文献