Cover-incomparability graphs and chordal graphs

The problem of recognizing cover-incomparability graphs (i.e. the graphs obtained from posets as the edge-union of their covering and incomparability graph) was shown to be NP-complete in general [J. Maxová, P. Pavlíkova, A. Turzík, On the complexity of cover-incomparability graphs of posets, Order 26 (2009) 229-236], while it is for instance clearly polynomial within trees. In this paper we concentrate on (classes of) chordal graphs, and show that any cover-incomparability graph that is a chordal graph is an interval graph. We characterize the posets whose cover-incomparability graph is a block graph, and a split graph, respectively, and also characterize the cover-incomparability graphs among block and split graphs, respectively. The latter characterizations yield linear time algorithms for the recognition of block and split graphs, respectively, that are cover-incomparability graphs.     

Characterizations and recognition of circular-arc graphs and subclasses: A survey

Circular graphs are intersection graphs of arcs on a circle. These graphs are reported to have been studied since 1964, and they have been receiving considerable attention since a series of papers by Tucker in the 1970s. Various subclasses of circular-arc graphs have also been studied. Among these are the proper circular-arc graphs, unit circular-arc graphs, Helly circular-arc graphs and co-bipartite circular-arc graphs. Several characterizations and recognition algorithms have been formulated for circular-arc graphs and its subclasses. In particular, it should be mentioned that linear time algorithms are known for all these classes of graphs. In the present paper, we survey these characterizations and recognition algorithms, with emphasis on the linear time algorithms.     

Vertex coverings by monochromatic paths and cycles

We survey some results on covering the vertices of 2-colored complete graphs by two paths or by two cycles of different color. We show the role of these results in determining path Ramsey numbers and in algorithms for finding long monochromatic paths or cycles in 2-colored complete graphs.     

The graphs that have antivoltages using groups of small order

Given a group $\Gamma$ of order at most six, we characterize the graphs that have $\Gamma$-antivoltages and also determine the list of minor-minimal graphs that have no $\Gamma$-antivoltage. Our characterizations yield polynomial-time recognition algorithms for such graphs.     

Oriented bipartite graphs and the Goldbach graph

In this paper, we study oriented bipartite graphs. In particular, we introduce “bitransitive” graphs. Several characterizations of bitransitive bitournaments are obtained. We show that bitransitive bitounaments are equivalent to acyclic bitournaments. As applications, we characterize acyclic bitournaments with Hamiltonian paths, determine the number of non-isomorphic acyclic bitournaments of a given order, and solve the graph-isomorphism problem in linear time for acyclic bitournaments. Next, we prove the well-known Caccetta-Häggkvist Conjecture for oriented bipartite graphs in some cases for which it is unsolved, in general, for oriented graphs. We also introduce the concept of undirected as well as oriented “odd-even” graphs. We characterize bipartite graphs and acyclic oriented bipartite graphs in terms of them. In fact, we show that any bipartite graph (acyclic oriented bipartite graph) can be represented by some odd-even graph (oriented odd-even graph). We obtain some conditions for connectedness of odd-even graphs. This study of odd-even graphs and their connectedness is motivated by a special family of odd-even graphs which we call “Goldbach graphs”. We show that the famous Goldbach's conjecture is equivalent to the connectedness of Goldbach graphs. Several other number theoretic conjectures (e.g., the twin prime conjecture) are related to various parameters of Goldbach graphs, motivating us to study the nature of vertex-degrees and independent sets of these graphs. Finally, we observe Hamiltonian properties of some odd-even graphs related to Goldbach graphs for a small number of vertices.     

Biclique-Helly Graphs

A graph is biclique-Helly when its family of (maximal) bicliques is a Helly family. We describe characterizations for biclique-Helly graphs, leading to polynomial time recognition algorithms. In addition, we relate biclique-Helly graphs to the classes of clique-Helly, disk-Helly and neighborhood-Helly graphs.     

Highly-connected planar cubic graphs with few or many Hamilton cycles

In this paper we consider the number of Hamilton cycles in planar cubic graphs of high cyclic edge-connectivity, answering two questions raised by Chia and Thomassen (2012) about extremal graphs in these families. In particular, we find families of cyclically 5-edge-connected planar cubic graphs with more Hamilton cycles than the generalized Petersen graphs $P(2n,2)$. The graphs themselves are fullerene graphs that correspond to certain carbon molecules known as nanotubes—more precisely, the family consists of the zigzag nanotubes of (fixed) width 5and increasing length. In order to count the Hamilton cycles in the nanotubes, we develop methods inspired by the transfer matrices of statistical physics. We outline how these methods can be adapted to count the Hamilton cycles in nanotubes of greater (but still fixed) width, with the caveat that the resulting expressions involve matrix powers. We also consider cyclically 4-edge-connected planar cubic graphs with few Hamilton cycles, and exhibit an infinite family of such graphs each with exactly 4 Hamilton cycles. Finally we consider the “other extreme” for these two classes of graphs, thus investigating cyclically 4-edge-connected planar cubic graphs with many Hamilton cycles and the cyclically 5-edge-connected planar cubic graphs with few Hamilton cycles. In each of these cases, we present partial results, examples and conjectures regarding the graphs with few or many Hamilton cycles.     

赋权图中的路和圈

本文研究了赋权图中的最长路和最长圈,将关于非赋权图中最长路和最长圈的一些结果推广到赋权图上.     

Regular path decompositions of odd regular graphs

Kotzig asked in 1979 what are necessary and sufficient conditions for a d‐regular simple graph to admit a decomposition into paths of length d for odd d>3. For cubic graphs, the existence of a 1‐factor is both necessary and sufficient. Even more, each 1‐factor is extendable to a decomposition of the graph into paths of length 3 where the middle edges of the paths coincide with the 1‐factor. We conjecture that existence of a 1‐factor is indeed a sufficient condition for Kotzig's problem. For general odd regular graphs, most 1‐factors appear to be extendable and we show that for the family of simple 5‐regular graphs with no cycles of length 4, all 1‐factors are extendable. However, for d>3 we found infinite families of d‐regular simple graphs with non‐extendable 1‐factors. Few authors have studied the decompositions of general regular graphs. We present examples and open problems; in particular, we conjecture that in planar 5‐regular graphs all 1‐factors are extendable. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 114–128, 2010     

On the semi-perfect elimination

We give algorithmic characterizations of two classes of graphs, for which every ordering produced by the Lexicographic Breadth-First Search and the Maximum Cardinality Search, respectively, satisfies a prescribed property. These characterizations allow us to design linear-time optimization algorithms for these classes of graphs.     

Locally finite graphs with ends: A topological approach, II. Applications

This paper is the second of three parts of a comprehensive survey of a newly emerging field: a topological approach to the study of locally finite graphs that crucially incorporates their ends. Topological arcs and circles, which may pass through ends, assume the role played in finite graphs by paths and cycles. The first two parts of the survey together provide a suitable entry point to this field for new readers; they are available in combined form from the ArXiv [20]. They are complemented by a third part [31], which looks at the theory from an algebraic-topological point of view.The topological approach indicated above has made it possible to extend to locally finite graphs many classical theorems of finite graph theory that do not extend verbatim. This second part of the survey concentrates on these applications, many of which solve problems or extend earlier work of Thomassen on infinite graphs. Numerous new problems are suggested.     

Characterizations of totally balanced matrices

A (0,1)-matrix is totally balanced if it does not contain as a submatrix the incidence matrix of any cycle of length at least 3. Several alternative characterizations of these matrices are presented. These characterizations follow from properties of strongly chordal graphs, studied by Farber, and maximal totally balanced matrices, studied by Anstee. Using these characterizations, efficient recognition algorithms for totally balanced matrices are presented. In addition, a new completion algorithm for building a maximal totally balanced matrix from an arbitrary totally balanced matrix follows from these results.     

Parallel Algorithms for Hierarchical Clustering and Applications to Split Decomposition and Parity Graph Recognition

We present efficient (parallel) algorithms for two hierarchical clustering heuristics. We point out that these heuristics can also be applied to solving some algorithmic problems in graphs, including split decomposition. We show that efficient parallel split decomposition induces an efficient parallel parity graph recognition algorithm. This is a consequence of the result of S. Cicerone and D. Di Stefano [[7]] that parity graphs are exactly those graphs that can be split decomposed into cliques and bipartite graphs.     

Periodic paths on nonautonomous graphs

We define nonautonomous graphs as a class of dynamic graphs in discrete time whose time-dependence consists in connecting or disconnecting edges. We study periodic paths in these graphs, and the associated zeta functions. Based on the analytic properties of these zeta functions we obtain explicit formulae for the number of n-periodic paths, as the sum of the nth powers of some specific algebraic numbers.     

Planar Hypohamiltonian Graphs on 40 Vertices

A graph is hypohamiltonian if it is not Hamiltonian, but the deletion of any single vertex gives a Hamiltonian graph. Until now, the smallest known planar hypohamiltonian graph had 42 vertices, a result due to Araya and Wiener. That result is here improved upon by 25 planar hypohamiltonian graphs of order 40, which are found through computer‐aided generation of certain families of planar graphs with girth 4 and a fixed number of 4‐faces. It is further shown that planar hypohamiltonian graphs exist for all orders greater than or equal to 42. If Hamiltonian cycles are replaced by Hamiltonian paths throughout the definition of hypohamiltonian graphs, we get the definition of hypotraceable graphs. It is shown that there is a planar hypotraceable graph of order 154 and of all orders greater than or equal to 156. We also show that the smallest planar hypohamiltonian graph of girth 5 has 45 vertices.     

Even and odd holes in cap‐free graphs

It is an old problem in graph theory to test whether a graph contains a chordless cycle of length greater than three (hole) with a specific parity (even, odd). Studying the structure of graphs without odd holes has obvious implications for Berge's strong perfect graph conjecture that states that a graph G is perfect if and only if neither G nor its complement contain an odd hole. Markossian, Gasparian, and Reed have proven that if neither G nor its complement contain an even hole, then G is β‐perfect. In this article, we extend the problem of testing whether G(V, E) contains a hole of a given parity to the case where each edge of G has a label odd or even. A subset of E is odd (resp. even) if it contains an odd (resp. even) number of odd edges. Graphs for which there exists a signing (i.e., a partition of E into odd and even edges) that makes every triangle odd and every hole even are called even‐signable. Graphs that can be signed so that every triangle is odd and every triangle is odd and every hole is odd are called odd‐signable. We derive from a theorem due to Truemper co‐NP characterizations of even‐signable and odd‐signable graphs. A graph is strongly even‐signable if it can be signed so that every cycle of length ≥ 4 with at most one chord is even and every triangle is odd. Clearly a strongly even‐signable graph is even‐signable as well. Graphs that can be signed so that cycles of length four with one chord are even and all other cycles with at most one chord are odd are called strongly odd‐signable. Every strongly odd‐signable graph is odd‐signable. We give co‐NP characterizations for both strongly even‐signable and strongly odd‐signable graphs. A cap is a hole together with a node, which is adjacent to exactly two adjacent nodes on the hole. We derive a decomposition theorem for graphs that contain no cap as induced subgraph (cap‐free graphs). Our theorem is analogous to the decomposition theorem of Burlet and Fonlupt for Meyniel graphs, a well‐studied subclass of cap‐free graphs. If a graph is strongly even‐signable or strongly odd‐signable, then it is cap‐free. In fact, strongly even‐signable graphs are those cap‐free graphs that are even‐signable. From our decomposition theorem, we derive decomposition results for strongly odd‐signable and strongly even‐signable graphs. These results lead to polynomial recognition algorithms for testing whether a graph belongs to one of these classes. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 289–308, 1999     

On minimal forbidden subgraph characterizations of balanced graphs

A graph is balanced if its clique-matrix contains no edge–vertex incidence matrix of an odd chordless cycle as a submatrix. While a forbidden induced subgraph characterization of balanced graphs is known, there is no such characterization by minimal forbidden induced subgraphs. In this work, we provide minimal forbidden induced subgraph characterizations of balanced graphs restricted to graphs that belong to one of the following graph classes: complements of bipartite graphs, line graphs of multigraphs, and complements of line graphs of multigraphs. These characterizations lead to linear-time recognition algorithms for balanced graphs within the same three graph classes.     

Improved algorithms for replacement paths problems in restricted graphs

We present near-optimal algorithms for two problems related to finding the replacement paths for edges with respect to shortest paths in sparse graphs. The problems essentially study how the shortest paths change as edges on the path fail, one at a time. Our technique improves the existing bounds for these problems on directed acyclic graphs, planar graphs, and non-planar integer-edge-weighted graphs.     

Unit Interval Graphs of Open and Closed Intervals

We give two structural characterizations of the class of finite intersection graphs of the open and closed real intervals of unit length. This class is a proper superclass of the well‐known unit interval graphs.     

Heavy fans, cycles and paths in weighted graphs of large connectivity

A set of paths joining a vertex y and a vertex set L is called (y,L)-fan if any two of the paths have only y in common, and its width is the number of paths forming it. In weighted graphs, it is known that the existence of heavy fan is useful to find a heavy cycle containing some specified vertices.In this paper, we show the existence of heavy fans with large width containing some specified vertices in weighted graphs of large connectivity, which is a weighted analogue of Perfect's theorem. Using this, in 3-connected weighted graphs, we can find heavy cycles containing three specified vertices, and also heavy paths joining two specified vertices containing two more specified vertices. These results extend the previous results in 2-connected weighted graphs to 3-connected weighted graphs.