Search

Canonical decompositions, such as the Gallai–Edmonds and Dulmage–Mendelsohn decompositions, are a series of structure theorems that form the foundation of matching theory. The classical Kotzig–Lovász decomposition is a canonical decomposition applicable to a special class of graphs with perfect matchings, called factor-connected graphs, and is famous for its contribution to the studies of perfect matching polytopes and lattices. Recently, this decomposition has been generalized for general graphs with perfect matchings; this generalized decomposition is called the general Kotzig–Lovász decomposition. In fact, this generalized decomposition can be presented as a component of a more composite canonical decomposition called the Basilica decomposition. As such, the general Kotzig–Lovász decomposition has contributed to the derivation of various new results in matching theory, such as an alternative proof of the tight cut lemma and a characterization of maximal barriers in general graphs. Joins in grafts, also known as T -joins in graphs, is a classical concept in combinatorics and is a generalization of perfect matchings in terms of parity. More precisely, minimum joins and grafts are generalizations of perfect matchings and graphs with perfect matchings, respectively. Under the analogy between matchings and joins, analogues of the canonical decompositions for grafts are expected to be strong and fundamental tools for studying joins. In this paper, we provide a generalization of the general Kotzig–Lovász decomposition for arbitrary grafts. Our result also contains Sebö's generalization of the classical Kotzig–Lovász decomposition for factor-connected grafts. From our results in this paper, a generalization of the Dulmage–Mendelsohn decomposition, which is originally a classical canonical decomposition for bipartite graphs, has been obtained for bipartite grafts. This paper is the first of a series of papers that establish a generalization of the Basilica decomposition for grafts. [ABSTRACT FROM AUTHOR]

Abstract: In this note we present House of Graphs (http://hog.grinvin.org) which is a new database of graphs. The key principle is to have a searchable database and offer–next to complete lists of some graph classes–also a list of special graphs that have already turned out to be interesting and relevant in the study of graph theoretic problems or as counterexamples to conjectures. This list can be extended by users of the database. [Copyright &y& Elsevier]

Abstract: Zero forcing (also called graph infection) on a simple, undirected graph is based on the color-change rule: if each vertex of is colored either white or black, and vertex is a black vertex with only one white neighbor , then change the color of to black. A minimum zero forcing set is a set of black vertices of minimum cardinality that can color the entire graph black using the color change rule. The propagation time of a zero forcing set of graph is the minimum number of steps that it takes to force all the vertices of black, starting with the vertices in black and performing independent forces simultaneously. The minimum and maximum propagation times of a graph are taken over all minimum zero forcing sets of the graph. It is shown that a connected graph of order at least two has more than one minimum zero forcing set realizing minimum propagation time. Graphs having extreme minimum propagation times , , and are characterized, and results regarding graphs having minimum propagation time 1 are established. It is shown that the diameter is an upper bound for maximum propagation time for a tree, but in general propagation time and diameter of a graph are not comparable. [Copyright &y& Elsevier]

Abstract: Consider the following generalization of the sequential group testing problem for 2 defective items, which is suggested by Aigner (1988) in : Suppose a graph contains one defective edge . Find the endpoints of by testing whether a subset of vertices of cardinality at most 2 contains at least one of the endpoints of or not. What is then the minimum number of tests, which are needed in the worst case to identify ? In Gerzen (2009) , this problem was partially solved by deriving sharp lower and upper bounds for . In addition, it was proved that the determination of is an NP-complete problem. Among others, it was shown that the inequality holds for graphs with 2-complexity and the edge set . In the present paper, we study the class of graphs for which this inequality is sharp and characterize these graphs in several ways. We suppose that for those graphs the 2-complexity can be computed in polynomial time by means of this characterization. [Copyright &y& Elsevier]

Abstract: The Harary index is defined as the sum of reciprocals of distances between all pairs of vertices of a connected graph. For a connected graph and two nonadjacent vertices and in of , recall that is the supergraph formed from by adding an edge between vertices and . Denote the Harary index of and by and , respectively. We obtain lower and upper bounds on , and characterize the equality cases in those bounds. Finally, in this paper, we present some lower and upper bounds on the Harary index of graphs with different parameters, such as clique number and chromatic number, and characterize the extremal graphs at which the lower or upper bounds on the Harary index are attained. [Copyright &y& Elsevier]

Abstract: We introduce a new type of order of sets of vertices. Using this concept, we describe the structure and the relationship between chordal, interval, cocomparability, and asteriodal triple-free graphs. [Copyright &y& Elsevier]

Abstract: We theoretically analyze the ‘cops and robber’ game for the first time in a multidimensional grid. It is shown that in an -dimensional grid, at least cops are necessary if one wants to catch the robber for all possible initial configurations. We also present a set of cop strategies for which cops are provably sufficient to catch the robber. Further, we revisit the game in a two-dimensional grid and provide an independent proof of the fact that the robber can be caught even by a single cop under certain conditions. [ABSTRACT FROM AUTHOR]

Abstract: We consider a generalization of the firefighter problem where the number of firefighters available per time step t is not a constant. We show that if the number of firefighters available is periodic in t and the average number per time period exceeds , then a fire starting at any finite number of vertices in the two dimensional infinite grid graph can always be contained. [Copyright &y& Elsevier]

Abstract: 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 () is requested. [Copyright &y& Elsevier]

Abstract: We study a robustness model for the minimum coloring problem, where any vertex of the input-graph has some presence probability . We show that, under this model, the original coloring problem gives rise to a new coloring version (called Probabilistic Min Coloring) where the objective becomes to determine a partition of into independent sets , that minimizes the quantity , where, for any independent set , . We show that Probabilistic Min Coloring is NP-hard and design a polynomial time approximation algorithm achieving non-trivial approximation ratio. We then focus ourselves on probabilistic coloring of bipartite graphs and show that the problem of determining the best k-coloring (called Probabilistic Min -Coloring) is NP-hard, for any . We finally study Probabilistic Min Coloring and Probabilistic Min -Coloring in a particular family of bipartite graphs that plays a crucial role in the proof of the NP-hardness result just mentioned, and in complements of bipartite graphs. [Copyright &y& Elsevier]

It is known that the independence number of a connected claw-free graph G of order n is at most (n+1)/2. We improve this result by showing that this bound still holds for the upper irredundance number IR(G). We characterize the connected claw-free graphs for which IR(G)=(n+1)/2 and give some properties of those graphs for which IR(G)=n/2 if n is even or IR(G)=(n−1)/2 if n is odd. [Copyright &y& Elsevier]