Partial characterizations of circular‐arc graphs

A circular‐arc graph is the intersection graph of a family of arcs on a circle. A characterization by forbidden induced subgraphs for this class of graphs is not known, and in this work we present a partial result in this direction. We characterize circular‐arc graphs by a list of minimal forbidden induced subgraphs when the graph belongs to any of the following classes: P₄ ‐free graphs, paw‐free graphs, claw‐free chordal graphs and diamond‐free graphs. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 289–306, 2009     

Two-ended regular median graphs

We show that regular median graphs of linear growth are the Cartesian product of finite hypercubes with the two-way infinite path. Such graphs are Cayley graphs and have only two ends.For cubic median graphs G the condition of linear growth can be weakened to the condition that G has two ends. For higher degree the relaxation to two-ended graphs is not possible, which we demonstrate by an example of a median graph of degree four that has two ends, but nonlinear growth.     

Polar cographs

Polar graphs are a natural extension of some classes of graphs like bipartite graphs, split graphs and complements of bipartite graphs. A graph is (s,k)-polar if there exists a partition A,B of its vertex set such that A induces a complete s-partite graph (i.e., a collection of at most s disjoint stable sets with complete links between all sets) and B a disjoint union of at most k cliques (i.e., the complement of a complete k-partite graph).Recognizing a polar graph is known to be NP-complete. These graphs have not been extensively studied and no good characterization is known. Here we consider the class of polar graphs which are also cographs (graphs without induced path on four vertices). We provide a characterization in terms of forbidden subgraphs. Besides, we give an algorithm in time O(n) for finding a largest induced polar subgraph in cographs; this also serves as a polar cograph recognition algorithm. We examine also the monopolar cographs which are the (s,k)-polar cographs where min(s,k)?1. A characterization of these graphs by forbidden subgraphs is given. Some open questions related to polarity are discussed.     

On Finite 2‐Path‐Transitive Graphs

The class of graphs that are 2‐path‐transitive but not 2‐arc‐transitive is investigated. The amalgams for such graphs are determined, and structural information regarding the full automorphism groups is given. It is then proved that a graph is 2‐path‐transitive but not 2‐arc‐transitive if and only if its line graph is half‐arc‐transitive, thus providing a method for constructing new families of half‐arc‐transitive graphs. © 2012 Wiley Periodicals, Inc. J. Graph Theory 73: 225–237, 2013     

Tree 3-spanners in 2-sep directed path graphs: Characterization, recognition, and construction

A spanning tree T of a graph G is called a treet-spanner, if the distance between any two vertices in T is at most t-times their distance in G. A graph that has a tree t-spanner is called a treet-spanner admissible graph. The problem of deciding whether a graph is tree t-spanner admissible is NP-complete for any fixed t≥4, and is linearly solvable for t=1 and t=2. The case t=3 still remains open. A directed path graph is called a 2-sep directed path graph if all of its minimal a−b vertex separator for every pair of non-adjacent vertices a and b are of size two. Le and Le [H.-O. Le, V.B. Le, Optimal tree 3-spanners in directed path graphs, Networks 34 (2) (1999) 81-87] showed that directed path graphs admit tree 3-spanners. However, this result has been shown to be incorrect by Panda and Das [B.S. Panda, Anita Das, On tree 3-spanners in directed path graphs, Networks 50 (3) (2007) 203-210]. In fact, this paper observes that even the class of 2-sep directed path graphs, which is a proper subclass of directed path graphs, need not admit tree 3-spanners in general. It, then, presents a structural characterization of tree 3-spanner admissible 2-sep directed path graphs. Based on this characterization, a linear time recognition algorithm for tree 3-spanner admissible 2-sep directed path graphs is presented. Finally, a linear time algorithm to construct a tree 3-spanner of a tree 3-spanner admissible 2-sep directed path graph is proposed.     

Greedily constructing Hamiltonian paths, Hamiltonian cycles and maximum linear forests

There are various greedy schemas to construct a maximal path in a given input graph. Associated with each such schema is the family of graphs where it always results a path of maximum length, or a Hamiltonian path/cycle, if there exists one. Considerable amount of work has been carried out, regarding the characterization and recognition problems of such graphs. We present here a systematic listing of previous results of this type and fill up most of the remaining empty entries.     

Forbidden induced subgraph characterizations of subclasses and variations of perfect graphs: A survey

A graph is perfect if the chromatic number is equal to the clique number for every induced subgraph of the graph. Perfect graphs were defined by Berge in the sixties. In this survey we present known results about partial characterizations by forbidden induced subgraphs of different graph classes related to perfect graphs. We analyze a variation of perfect graphs, clique-perfect graphs, and two subclasses of perfect graphs, coordinated graphs and balanced graphs.     

Solving the path cover problem on circular-arc graphs by using an approximation algorithm

A path cover of a graph G=(V,E) is a family of vertex-disjoint paths that covers all vertices in V. Given a graph G, the path cover problem is to find a path cover of minimum cardinality. This paper presents a simple O(n)-time approximation algorithm for the path cover problem on circular-arc graphs given a set of n arcs with endpoints sorted. The cardinality of the path cover found by the approximation algorithm is at most one more than the optimal one. By using the result, we reduce the path cover problem on circular-arc graphs to the Hamiltonian cycle and Hamiltonian path problems on the same class of graphs in O(n) time. Hence the complexity of the path cover problem on circular-arc graphs is the same as those of the Hamiltonian cycle and Hamiltonian path problems on circular-arc graphs.     

Matching theory and Barnette's conjecture

Barnette's Conjecture claims that all cubic, 3-connected, planar, bipartite graphs are Hamiltonian. We give a translation of this conjecture into the matching-theoretic setting. This allows us to relax the requirement of planarity to give the equivalent conjecture that all cubic, 3-connected, Pfaffian, bipartite graphs are Hamiltonian.A graph, other than the path of length three, is a brace if it is bipartite and any two disjoint edges are part of a perfect matching. Our perspective allows us to observe that Barnette's Conjecture can be reduced to cubic, planar braces. We show a similar reduction to braces for cubic, 3-connected, bipartite graphs regarding four stronger versions of Hamiltonicity. Note that in these cases we do not need planarity.As a practical application of these results, we provide some supplements to a generation procedure for cubic, 3-connected, planar, bipartite graphs discovered by Holton et al. (1985) [14]. These allow us to check whether a graph we generated is a brace.     

(向量)R_n和(向量)G_n的有向优美性

优美图可用在图论中的某些H-分解问题中,很多人研究无向图的优美标号.研究有向优美标号,通过对阶数奇偶性的讨论,给出了n(≥2)阶有向路(向量)P_n和n(≥3)阶有向(向量)C_n圈是有向优美的充分条件.     

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.     

Characterizing subgraphs of Hamming graphs

Cartesian products of complete graphs are known as Hamming graphs. Using embeddings into Cartesian products of quotient graphs we characterize subgraphs, induced subgraphs, and isometric subgraphs of Hamming graphs. For instance, a graph G is an induced subgraph of a Hamming graph if and only if there exists a labeling of E(G) fulfilling the following two conditions: (i) edges of a triangle receive the same label; (ii) for any vertices u and v at distance at least two, there exist two labels which both appear on any induced u, υ‐path. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 302–312, 2005     

The structure of Leavitt path algebras and the Invariant Basis Number property

In this paper, we provide the structure of the Leavitt path algebra of a finite graph via some step-by-step process of source eliminations, and restate Kanuni and Özaydin's nice criterion for Leavitt path algebras of finite graphs having Invariant Basis Number via matrix-theoretic language. Consequently, we give a matrix-theoretic criterion for the Leavitt path algebra of a finite graph having Invariant Basis Number in terms of a sequence of source eliminations. Using these results, we show certain classes of finite graphs for which Leavitt path algebras have Invariant Basis Number, as well as investigate the Invariant Basis Number property of Leavitt path algebras of certain Cayley graphs of finite groups.     

Finding a minimum path cover of a distance-hereditary graph in polynomial time

A path cover of a graph G=(V,E) is a set of pairwise vertex-disjoint paths such that the disjoint union of the vertices of these paths equals the vertex set V of G. The path cover problem is, given a graph, to find a path cover having the minimum number of paths. The path cover problem contains the Hamiltonian path problem as a special case since finding a path cover, consisting of a single path, corresponds directly to the Hamiltonian path problem. A graph is a distance-hereditary graph if each pair of vertices is equidistant in every connected induced subgraph containing them. The complexity of the path cover problem on distance-hereditary graphs has remained unknown. In this paper, we propose the first polynomial-time algorithm, which runs in O(|V|⁹) time, to solve the path cover problem on distance-hereditary graphs.     

Marginal AMP chain graphs

We present a new family of models that is based on graphs that may have undirected, directed and bidirected edges. We name these new models marginal AMP (MAMP) chain graphs because each of them is Markov equivalent to some AMP chain graph under marginalization of some of its nodes. However, MAMP chain graphs do not only subsume AMP chain graphs but also multivariate regression chain graphs. We describe global and pairwise Markov properties for MAMP chain graphs and prove their equivalence for compositional graphoids. We also characterize when two MAMP chain graphs are Markov equivalent.For Gaussian probability distributions, we also show that every MAMP chain graph is Markov equivalent to some directed and acyclic graph with deterministic nodes under marginalization and conditioning on some of its nodes. This is important because it implies that the independence model represented by a MAMP chain graph can be accounted for by some data generating process that is partially observed and has selection bias. Finally, we modify MAMP chain graphs so that they are closed under marginalization for Gaussian probability distributions. This is a desirable feature because it guarantees parsimonious models under marginalization.     

Matching signatures and Pfaffian graphs

Perfect matchings of k-Pfaffian graphs may be enumerated in polynomial time on the number of vertices, for fixed k. In general, this enumeration problem is #P-complete. We give a Composition Theorem of 2r-Pfaffian graphs from r Pfaffian spanning subgraphs. Constructions of k-Pfaffian graphs known prior to this seem to be of a very different and essentially topological nature. We apply our Composition Theorem to produce a bipartite graph on 10 vertices that is 6-Pfaffian but not 4-Pfaffian. This is a counter-example to a conjecture of Norine (2009) [8], which states that the Pfaffian number of a graph is a power of four.     

On bipartite graphs of diameter 3 and defect 2

We consider bipartite graphs of degree Δ≥2, diameter D=3, and defect 2 (having 2 vertices less than the bipartite Moore bound). Such graphs are called bipartite (Δ, 3, ?2) ‐graphs. We prove the uniqueness of the known bipartite (3, 3, ?2) ‐graph and bipartite (4, 3, ?2)‐graph. We also prove several necessary conditions for the existence of bipartite (Δ, 3, ?2) ‐graphs. The most general of these conditions is that either Δ or Δ?2 must be a perfect square. Furthermore, in some cases for which the condition holds, in particular, when Δ=6 and Δ=9, we prove the non‐existence of the corresponding bipartite (Δ, 3, ?2)‐graphs, thus establishing that there are no bipartite (Δ, 3, ?2)‐graphs, for 5≤Δ≤10. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 271–288, 2009     

Every 3‐connected claw‐free Z8‐free graph is Hamiltonian

A biclique of a graph G is a maximal induced complete bipartite subgraph of G. Given a graph G, the biclique matrix of G is a {0,1,?1} matrix having one row for each biclique and one column for each vertex of G, and such that a pair of 1, ?1 entries in a same row corresponds exactly to adjacent vertices in the corresponding biclique. We describe a characterization of biclique matrices, in similar terms as those employed in Gilmore's characterization of clique matrices. On the other hand, the biclique graph of a graph is the intersection graph of the bicliques of G. Using the concept of biclique matrices, we describe a Krausz‐type characterization of biclique graphs. Finally, we show that every induced P₃ of a biclique graph must be included in a diamond or in a 3‐fan and we also characterize biclique graphs of bipartite graphs. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 1–16, 2010     

On conservative and supermagic graphs

A graph is called supermagic if it admits a labelling of the edges by pairwise different consecutive positive integers such that the sum of the labels of the edges incident with a vertex is independent of the particular vertex. A graph G is called conservative if it admits an orientation and a labelling of the edges by integers {1,…,|E(G)|} such that at each vertex the sum of the labels on the incoming edges is equal to the sum of the labels on the outgoing edges. In this paper we deal with conservative graphs and their connection with the supermagic graphs. We introduce a new method to construct supermagic graphs using conservative graphs. Inter alia we show that the union of some circulant graphs and regular complete multipartite graphs are supermagic.