共查询到20条相似文献,搜索用时 31 毫秒
1.
Jie Hu Guanghui Wang Jianliang Wu Donglei Yang Xiaowei Yu 《Discrete Mathematics》2019,342(5):1392-1402
Let be a positive integer. An adjacent vertex distinguishing (for short, AVD) total--coloring of a graph is a proper total--coloring of such that any two adjacent vertices have different color sets, where the color set of a vertex contains the color of and the colors of its incident edges. It was conjectured that any graph with maximum degree has an AVD total-()-coloring. The conjecture was confirmed for any graph with maximum degree at most 4 and any planar graph with maximum degree at least 10. In this paper, we verify the conjecture for all planar graphs with maximum degree at least 9. Moreover, we prove that any planar graph with maximum degree at least 10 has an AVD total-()-coloring and the bound is sharp. 相似文献
2.
《Operations Research Letters》2020,48(3):266-270
Given a strongly connected, mixed graph with costs on its edges and arcs, the mixed postman problem is to find a minimum cost closed walk traversing its edges and arcs at least once. This problem is NP-hard even on planar graphs but is solvable in polynomial time on series–parallel graphs. We give dynamic programming algorithms for the mixed postman problem and other similar problems on series–parallel graphs with vertices and edges and arcs. 相似文献
3.
4.
We give upper bounds for the edge integrity and the vertex integrity of -type nearest neighbor graphs in . For the order of a graph, examples are constructed to show that the bounds are best possible in the parameters and . The results follow from decompositions that are shown for certain graphs that possess small edge or vertex separators. A vertex separator theorem for nearest neighbor graphs is known, and an edge separator theorem is shown. We also apply the decompositions to obtain upper bounds for the edge integrity of planar graphs, graphs of fixed genus, and trees. 相似文献
5.
6.
《Discrete Mathematics》2019,342(4):1195-1212
A graph is -saturated for a graph , if does not contain a copy of but adding any new edge to results in such a copy. An -saturated graph on a given number of vertices always exists and the properties of such graphs, for example their highest density, have been studied intensively.A graph is -induced-saturated if does not have an induced subgraph isomorphic to , but adding an edge to from its complement or deleting an edge from results in an induced copy of . It is not immediate anymore that -induced-saturated graphs exist. In fact, Martin and Smith (2012) showed that there is no -induced-saturated graph. Behrens et al. (2016) proved that if belongs to a few simple classes of graphs such as a class of odd cycles of length at least 5, stars of size at least 2, or matchings of size at least 2, then there is an -induced-saturated graph.This paper addresses the existence question for -induced-saturated graphs. It is shown that Cartesian products of cliques are -induced-saturated graphs for in several infinite families, including large families of trees. A complete characterization of all connected graphs for which a Cartesian product of two cliques is an -induced-saturated graph is given. Finally, several results on induced saturation for prime graphs and families of graphs are provided. 相似文献
7.
8.
《Discrete Mathematics》2021,344(12):112622
A Deza graph G with parameters is a k-regular graph with n vertices such that any two distinct vertices have b or a common neighbours. The children and of a Deza graph G are defined on the vertex set of G such that every two distinct vertices are adjacent in or if and only if they have a or b common neighbours, respectively. A strongly Deza graph is a Deza graph with strongly regular children. In this paper we give a spectral characterisation of strongly Deza graphs, show relationships between eigenvalues, and study strongly Deza graphs which are distance-regular. 相似文献
9.
A path decomposition of a graph is a collection of edge-disjoint paths of that covers the edge set of . Gallai (1968) conjectured that every connected graph on vertices admits a path decomposition of cardinality at most . Gallai’s Conjecture has been verified for many classes of graphs. In particular, Lovász (1968) verified this conjecture for graphs with at most one vertex with even degree, and Pyber (1996) verified it for graphs in which every cycle contains a vertex with odd degree. Recently, Bonamy and Perrett (2016) verified Gallai’s Conjecture for graphs with maximum degree at most 5, and Botler et al. (2017) verified it for graphs with treewidth at most 3. In this paper, we verify Gallai’s Conjecture for triangle-free planar graphs. 相似文献
10.
We consider the structure of -free subgraphs of graphs with high minimal degree. We prove that for every there exists an so that the following holds. For every graph with chromatic number from which one can delete an edge and reduce the chromatic number, and for every graph on vertices in which all degrees are at least , any subgraph of which is -free and contains the maximum number of copies of the complete graph is -colorable.We also consider several extensions for the case of a general forbidden graph of a given chromatic number, and for subgraphs maximizing the number of copies of balanced blowups of complete graphs. 相似文献
11.
For an integer , a graph is -hamiltonian if for any vertex subset with , is hamiltonian, and is -hamiltonian connected if for any vertex subset with , is hamiltonian connected. Thomassen in 1984 conjectured that every 4-connected line graph is hamiltonian (see Thomassen, 1986), and Ku?zel and Xiong in 2004 conjectured that every 4-connected line graph is hamiltonian connected (see Ryjá?ek and Vrána, 2011). In Broersma and Veldman (1987), Broersma and Veldman raised the characterization problem of -hamiltonian line graphs. In Lai and Shao (2013), it is conjectured that for , a line graph is -hamiltonian if and only if is -connected. In this paper we prove the following.(i) For an integer , the line graph of a claw-free graph is -hamiltonian if and only if is -connected.(ii) The line graph of a claw-free graph is 1-hamiltonian connected if and only if is 4-connected. 相似文献
12.
13.
14.
Given two graphs and , the maximum possible number of copies of in an -free graph on vertices is denoted by . We investigate the function , where denotes vertex disjoint copies of a fixed graph . Our results include cases when is a complete graph, cycle or a complete bipartite graph. 相似文献
15.
A graph is -colorable if it admits a vertex partition into a graph with maximum degree at most and a graph with maximum degree at most . We show that every -free planar graph is -colorable. We also show that deciding whether a -free planar graph is -colorable is NP-complete. 相似文献
16.
《Discrete Mathematics》2023,346(4):113288
Square coloring is a variant of graph coloring where vertices within distance two must receive different colors. When considering planar graphs, the most famous conjecture (Wegner, 1977) states that colors are sufficient to square color every planar graph of maximum degree Δ. This conjecture has been proven asymptotically for graphs with large maximum degree. We consider here planar graphs with small maximum degree and show that colors are sufficient, which improves the best known bounds when . 相似文献
17.
18.
An edge of a -connected graph is said to be -contractible if its contraction results in a -connected graph. A -connected graph without -contractible edge is said to be contraction critically -connected. Y. Egawa and W. Mader, independently, showed that the minimum degree of a contraction critical -connected graph is at most . Hence, the minimum degree of a contraction critical 8-connected graph is either 8 or 9. This paper shows that a graph is a contraction critical 8-connected graph with minimum degree 9 if and only if is the strong product of a contraction critical 4-connected graph and . 相似文献
19.