Sufficient conditions for a graph to be edge-colorable with maximum degree colors

We study properties of graphs related to the existence of certain vertex and edge partitions. These properties give sufficient conditions for a graph to be Class 1 (i.e., edge-colorable with maximum degree colors). We apply these conditions for solving the classification problem for graphs with acyclic core (the subgraph induced by the maximum degree vertices), and for subclasses of join graphs and cobipartite graphs.     

一类直径为2的极大平面图的Mostar指数

图G的Mostar指数定义为Mo(G)=∑uv∈Ε(G)|nu-nv|,其中nu表示在G中到顶点u的距离比到顶点v的距离近的顶点个数,nv表示到顶点v的距离比到顶点u的距离近的顶点个数.若一个图G的任两点之间的距离至多为2,且不是完全图,则称G是一个直径为2的图.已知直径为2点数至少为4的极大平面图的最小度为3或4.本文研究了直径为2且最小度为4的极大平面图的Mostar指数.具体说,若G是一个点数为n,直径为2,最小度为4的极大平面图,则(1)当n≤12时,Mostar指数被完全确定;(2)当n≥13时,4/3n2-44/3n+94/3≤Mo(G)≤2n2-16n+24,且达到上,下界的极图同时被找到.     

阶数极大的临界全控制图

称一个没有孤立点的图G 为临界全控制图, 如果G 满足对于任何一个不与悬挂点相邻的顶点v, G - v 的全控制数都小于G 的全控制数. 如果G 的全控制数记为γ_t, 则称这样的临界全控制图G 为γ_t- 临界的. 如果G 是γ_t- 临界的, 且阶数为n, 则n ≤ Δ(G)(γ_t(G)- 1) + 1, 其中Δ(G) 是G 的最大度. 本文将证明对γ_t = 3, 这个阶数的上界是紧的, 并给出所有满足n = Δ(G)(γ_t(G)- 1) + 1 的3-γ_t- 临界图.     

Cut Vertices and Degree One Vertices of Zero-Divisor Graphs

This article continues to examine cut vertices in the zero-divisor graphs of commutative rings with 1. The main result is that, with only seven known exceptions, the zero-divisor graph of a commutative ring has a cut vertex if and only if the graph has a degree one vertex. This naturally leads to an examination of the degree one vertices of zero-divisor graphs.     

Disjoint dominating and total dominating sets in graphs

It has been shown [M.A. Henning, J. Southey, A note on graphs with disjoint dominating and total dominating sets, Ars Combin. 89 (2008) 159-162] that every connected graph with minimum degree at least two that is not a cycle on five vertices has a dominating set D and a total dominating set T which are disjoint. We characterize such graphs for which D∪T necessarily contains all vertices of the graph and that have no induced cycle on five vertices.     

The firefighter problem for cubic graphs

We show that the firefighter problem is NP-complete for cubic graphs. We also show that given a rooted tree of maximum degree three in which every leaf is at the same distance from the root, it is NP-complete to decide whether or not there is a strategy that protects every leaf from the fire, which starts at the root. By contrast, we describe a polynomial time algorithm to decide if it is possible to save a given subset of the vertices of a graph with maximum degree three, provided the fire breaks out at a vertex of degree at most two.     

Eigenvalues of the Laplacian of a graph

Let G be a finite undirected graph with no loops or multiple edges. We define the Laplacian matrix of G,Δ(G)by Δ_ij= degree of vertex i and Δ_ij-1 if there is an edge between vertex i and vertex j. In this paper we relate the structure of the graph G to the eigenvalues of A(G): in particular we prove that all the eigenvalues of Δ(G) are non-negative, less than or equal to the number of vertices, and less than or equal to twice the maximum vertex degree. Precise conditions for equality are given.     

The satisfactory partition problem

The SATISFACTORY PARTITION problem consists in deciding if a given graph has a partition of its vertex set into two nonempty parts such that each vertex has at least as many neighbors in its part as in the other part. This problem was introduced by Gerber and Kobler [Partitioning a graph to satisfy all vertices, Technical report, Swiss Federal Institute of Technology, Lausanne, 1998; Algorithmic approach to the satisfactory graph partitioning problem, European J. Oper. Res. 125 (2000) 283-291] and further studied by other authors but its complexity remained open until now. We prove in this paper that SATISFACTORY PARTITION, as well as a variant where the parts are required to be of the same cardinality, are NP-complete. However, for graphs with maximum degree at most 4 the problem is polynomially solvable. We also study generalizations and variants of this problem where a partition into k nonempty parts (k?3) is requested.     

Degree conditions on claws and modified claws for hamiltonicity of graphs

Ore presented a degree condition involving every pair of nonadjacent vertices for a graph to be hamiltonian. Fan [New sufficient conditions for cycles in graphs, J. Combin. Theory Ser. B 37 (1984) 221-227] showed that not all the pairs of nonadjacent vertices are required, but only the pairs of vertices at the distance two suffice. Bedrossian et al. [A generalization of Fan's condition for hamiltonicity, pancyclicity, and hamiltonian connectedness, Discrete Math. 115 (1993) 39-50] improved Fan's result involving the pairs of vertices contained in an induced claw or an induced modified claw. On the other hand, Matthews and Sumner [Longest paths and cycles in K_1,3-free graphs, J. Graph Theory 9 (1985) 269-277] gave a minimum degree condition for a claw-free graph to be hamiltonian. In this paper, we give a new degree condition in an induced claw or an induced modified claw ensuring the hamiltonicity of graphs which extends both results of Bederossian et al. and Matthews and Sumner.     

Clique-critical graphs: Maximum size and recognition

The clique graph of G, K(G), is the intersection graph of the family of cliques (maximal complete sets) of G. Clique-critical graphs were defined as those whose clique graph changes whenever a vertex is removed. We prove that if G has m edges then any clique-critical graph in K^-1(G) has at most 2m vertices, which solves a question posed by Escalante and Toft [On clique-critical graphs, J. Combin. Theory B 17 (1974) 170-182]. The proof is based on a restatement of their characterization of clique-critical graphs. Moreover, the bound is sharp. We also show that the problem of recognizing clique-critical graphs is NP-complete.     

Bounds on Special Subsets in Graphs, Eigenvalues and Association Schemes

We give a bound on the sizes of two sets of vertices at a given minimum distance in a graph in terms of polynomials and the Laplace spectrum of the graph. We obtain explicit bounds on the number of vertices at maximal distance and distance two from a given vertex, and on the size of two equally large sets at maximal distance. For graphs with four eigenvalues we find bounds on the number of vertices that are not adjacent to a given vertex and that have µ common neighbours with that vertex. Furthermore we find that the regular graphs for which the bounds are tight come from association schemes.     

Cubic vertices in planar hypohamiltonian graphs

Thomassen showed in 1978 that every planar hypohamiltonian graph contains a cubic vertex. Equivalently, a planar graph with minimum degree at least 4 in which every vertex-deleted subgraph is hamiltonian, must be itself hamiltonian. By applying work of Brinkmann and the author, we extend this result in three directions. We prove that (i) every planar hypohamiltonian graph contains at least four cubic vertices, (ii) every planar almost hypohamiltonian graph contains a cubic vertex, which is not the exceptional vertex (solving a problem of the author raised in J. Graph Theory [79 (2015) 63–81]), and (iii) every hypohamiltonian graph with crossing number 1 contains a cubic vertex. Furthermore, we settle a recent question of Thomassen by proving that asymptotically the ratio of the minimum number of cubic vertices to the order of a planar hypohamiltonian graph vanishes.     

A polynomial algorithm for maximum weighted vertex packings on graphs without long odd cycles

The vertex packing problem for a given graph is to find a maximum number of vertices no two of which are joined by an edge. The weighted version of this problem is to find a vertex packingP such that the sum of the individual vertex weights is maximum. LetG be the family of graphs whose longest odd cycle is of length not greater than 2K + 1, whereK is any non-negative integer independent of the number (denoted byn) of vertices in the graph. We present an O(n ^2K+1) algorithm for the maximum weighted vertex packing problem for graphs inG 1. A by-product of this algorithm is an algorithm for piecing together maximum weighted packings on blocks to find maximum weighted packings on graphs that contain more than one block. We also give an O(n ^2K+3) algorithm for testing membership inG This work was supported by NSF grant ENG75-00568 to Cornell University. Some of the results of this paper have appeared in Hsu's unpublished Ph.D. dissertation [9].     

Precoloring extension on unit interval graphs

In the precoloring extension problem a graph is given with some of the vertices having preassigned colors and it has to be decided whether this coloring can be extended to a proper k-coloring of the graph. Answering an open question of Hujter and Tuza [Precoloring extension. III. Classes of perfect graphs, Combin. Probab. Comput. 5 (1) (1996) 35-56], we show that the precoloring extension problem is NP-complete on unit interval graphs.     

The elimination procedure for the competition number is not optimal

Given an acyclic digraph D, the competition graph C(D) is defined to be the undirected graph with V(D) as its vertex set and where vertices x and y are adjacent if there exists another vertex z such that the arcs (x,z) and (y,z) are both present in D. The competition number k(G) for an undirected graph G is the least number r such that there exists an acyclic digraph F on |V(G)|+r vertices where C(F) is G along with r isolated vertices. Kim and Roberts [The Elimination Procedure for the Competition Number, Ars Combin. 50 (1998) 97-113] introduced an elimination procedure for the competition number, and asked whether the procedure calculated the competition number for all graphs. We answer this question in the negative by demonstrating a graph where the elimination procedure does not calculate the competition number. This graph also provides a negative answer to a similar question about the related elimination procedure for the phylogeny number introduced by the current author in [S.G. Hartke, The Elimination Procedure for the Phylogeny Number, Ars Combin. 75 (2005) 297-311].     

Vertex-Disjoint Cycles Containing Specified Edges

Dirac and Ore-type degree conditions are given for a graph to contain vertex disjoint cycles each of which contains a previously specified edge. One set of conditions is given that imply vertex disjoint cycles of length at most 4, and another set of conditions are given that imply the existence of cycles that span all of the vertices of the graph (i.e. a 2-factor). The conditions are shown to be sharp and give positive answers to conjectures of Enomoto in [3] and Wang in [5]. Revised: July 28, 1999     

图的孤立断裂度

连通图G的孤立断裂度isc(G)=max{i(G-S)-|S|:S∈C(G)},其中i(G-S)是G-S中的孤立点数,C(G)是G的点割集.本文研究了孤立断裂度和图的其它一些参数的关系.讨论了孤立断裂度取特殊值的一些图,证明了圈、连通二部图、连通二部图的联图以及树和圈的补图的孤立断裂度都达到最小.给出了具有给定阶数和最大度的村的最大、最小孤立断裂度.     

Augmenting a graph of minimum degree 2 to have two disjoint total dominating sets

A total dominating set of a graph is a set of vertices such that every vertex is adjacent to a vertex in the set. We show that given a graph of order n with minimum degree at least 2, one can add at most edges such that the resulting graph has two disjoint total dominating sets, and this bound is best possible.     

Decomposition of cubic graphs related to Wegner’s conjecture

Thomassen formulated the following conjecture: Every 3-connected cubic graph has a red–blue vertex coloring such that the blue subgraph has maximum degree 1 (that is, it consists of a matching and some isolated vertices) and the red subgraph has minimum degree at least 1 and contains no 3-edge path. We prove the conjecture for Generalized Petersen graphs.We indicate that a coloring with the same properties might exist for any subcubic graph. We confirm this statement for all subcubic trees.     

Vertex covers and eternal dominating sets

The eternal domination problem requires a graph to be protected against an infinitely long sequence of attacks on vertices by guards located at vertices, the configuration of guards inducing a dominating set at all times. An attack at a vertex with no guard is defended by sending a guard from a neighboring vertex to the attacked vertex. We allow any number of guards to move to neighboring vertices at the same time in response to an attack. We compare the eternal domination number with the vertex cover number of a graph. One of our main results is that the eternal domination number is less than the vertex cover number of any graph of minimum degree at least two having girth at least nine.