Ascending Subgraph Decompositions of Tournaments of Order 6n + 3

In 1987, Alavi, Boals, Chartrand, Erdös, and Oellermann conjectured that all graphs have an ascending subgraph decomposition (ASD). Though several classes of graphs have been shown to have an ASD, the conjecture remains open. In this paper, we investigate the similar problem for tournaments. In particular, using Kirkman Triple Systems, we will show that all tournaments of order 6n + 3 have an ASD.     

Some graphs which have ascending subgraph decomposition

1.IntroductionIn[1],Alavietal.gavethefollowingdecompositionconjecture.Conjecture.LetGbeagraphwith("1')edges.ThentheedgesetofGcanbedecomposedintonsetsgeneratinggraphsGI,G2,'IG.suchthatIE(Gi)I=i(fori=1,2,',n)andGiisisomorphictoasubgraphofGi 1fori=1,2,'.)n--1.AgraphGthatcanbedecomposedasdescribedinConjecturewillbesaidtohaveanAscendingSubgraphDecomposition(AlsoabbreviatedasASD).ThesubgraphsGIIG2,',G.aresaidtobemembersofsuchadecomposition.Furthermore,ifeachGiisastar(matching,pat…     

Algebraic characterizations of outerplanar and planar graphs

A drawing of a graph in the plane is even if nonadjacent edges have an even number of intersections. Hanani’s theorem characterizes planar graphs as those graphs that have an even drawing. In this paper we present an algebraic characterization of graphs that have an even drawing. Together with Hanani’s theorem this yields an algebraic characterization of planar graphs. We will also present algebraic characterizations of subgraphs of paths, and of outerplanar graphs.     

Split Permutation Graphs

The class of split permutation graphs is the intersection of two important classes, the split graphs and permutation graphs. It also contains an important subclass, the threshold graphs. The class of threshold graphs enjoys many nice properties. In particular, these graphs have bounded clique-width and they are well-quasi-ordered by the induced subgraph relation. It is known that neither of these two properties is extendable to split graphs or to permutation graphs. In the present paper, we study the question of extendability of these two properties to split permutation graphs. We answer this question negatively with respect to both properties. Moreover, we conjecture that with respect to both of them the split permutation graphs constitute a critical class.     

Core-free,rank two coset geometries from edge-transitive bipartite graphs

It is known that the Levi graph of any rank two coset geometry is an edge-transitive graph, and thus coset geometries can be used to construct many edge transitive graphs. In this paper, we consider the reverse direction. Starting from edge-transitive graphs, we construct all associated core-free, rank two coset geometries. In particular, we focus on 3-valent and 4-valent graphs, and are able to construct coset geometries arising from these graphs. We summarize many properties of these coset geometries in a sequence of tables; in the 4-valent case we restrict to graphs that have relatively small vertex-stabilizers.     

Combinatorial optimization with 2-joins

A 2-join is an edge cutset that naturally appears in decomposition of several classes of graphs closed under taking induced subgraphs, such as perfect graphs and claw-free graphs. In this paper we construct combinatorial polynomial time algorithms for finding a maximum weighted clique, a maximum weighted stable set and an optimal coloring for a class of perfect graphs decomposable by 2-joins: the class of perfect graphs that do not have a balanced skew partition, a 2-join in the complement, nor a homogeneous pair. The techniques we develop are general enough to be easily applied to finding a maximum weighted stable set for another class of graphs known to be decomposable by 2-joins, namely the class of even-hole-free graphs that do not have a star cutset.We also give a simple class of graphs decomposable by 2-joins into bipartite graphs and line graphs, and for which finding a maximum stable set is NP-hard. This shows that having holes all of the same parity gives essential properties for the use of 2-joins in computing stable sets.     

Intrinsically linked signed graphs in projective space

We define a signed embedding of a signed graph into real projective space to be an embedding such that an embedded cycle is 0-homologous if and only if it is balanced. We characterize signed graphs that have a linkless signed embedding. In particular, we exhibit 46 graphs that form the complete minor-minimal set of signed graphs that contain a non-split link for every signed embedding. With one trivial exception, these graphs are derived from different signings of the seven Petersen family graphs.     

Circuit decompositions of join‐covered graphs

In this paper, we focus our attention on join‐covered graphs, that is, ±1‐weighted graphs, without negative circuits, in which every edge lies in a zero‐weight circuit. Join covered graphs are a natural generalization of matching‐covered graphs. Many important properties of matching covered graphs, such as the existence of a canonical partition, tight cut decomposition and ear decomposition, have been generalized to join covered graphs by A. Seb? [5]. In this paper we prove that any two edges of a join‐covered graph lie on a zero‐weight circuit (under an equivalent weighting), generalize this statement to an arbitrary number of edges, and characterize minimal bipartite join‐covered graphs. © 2009 Wiley Periodicals, Inc. J Graph Theory 62, 220–233, 2009     

关于双顶边星图的优美性

在文献[1]中,C.Hoede and H.Kuiper证明了所有的轮都是优美图;文献[2]又指出了所有的齿轮图也是优美图.本文将给出在齿轮图每个齿的顶端加上两条长度为1的边所得的图亦为优美图.     

Anticodes for the Grassman and bilinear forms graphs

In [2], L. Chihara proved that many infinite families of classical distance-regular graphs have no nontrivial perfect codes, including the Grassman graphs and the bilinear forms graphs. Here, we present a new proof of her result for these two families using Delsarte's anticode condition[3]. The technique is an extension of an approach taken by C. Roos [6] in the study of perfect codes in the Johnson graphs.     

On betweenness-uniform graphs

The betweenness centrality of a vertex of a graph is the fraction of shortest paths between all pairs of vertices passing through that vertex. In this paper, we study properties and constructions of graphs whose vertices have the same value of betweenness centrality (betweenness-uniform graphs); we show that this property holds for distanceregular graphs (which include strongly regular graphs) and various graphs obtained by graph cloning and local join operation. In addition, we show that, for sufficiently large n, there are superpolynomially many betweenness-uniform graphs on n vertices, and explore the structure of betweenness-uniform graphs having a universal or sub-universal vertex.     

Bipartite almost distance-hereditary graphs

The notion of distance-heredity in graphs has been extended to construct the class of almost distance-hereditary graphs (an increase of the distance by one unit is allowed by induced subgraphs). These graphs have been characterized in terms of forbidden induced subgraphs [M. Aïder, Almost distance-hereditary graphs, Discrete Math. 242 (1–3) (2002) 1–16]. Since the distance in bipartite graphs cannot increase exactly by one unit, we have to adapt this notion to the bipartite case.In this paper, we define the class of bipartite almost distance-hereditary graphs (an increase of the distance by two is allowed by induced subgraphs) and obtain a characterization in terms of forbidden induced subgraphs.     

An improved Moore bound and some new optimal families of mixed Abelian Cayley graphs

We consider the case in which mixed graphs (with both directed and undirected edges) are Cayley graphs of Abelian groups. In this case, some Moore bounds were derived for the maximum number of vertices that such graphs can attain. We first show these bounds can be improved if we know more details about the order of some elements of the generating set. Based on these improvements, we present some new families of mixed graphs. For every fixed value of the degree, these families have an asymptotically large number of vertices as the diameter increases. In some cases, the results obtained are shown to be optimal.     

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.     

The Hamiltonian connectivity of rectangular supergrid graphs

A Hamiltonian path of a graph is a simple path which visits each vertex of the graph exactly once. The Hamiltonian path problem is to determine whether a graph contains a Hamiltonian path. A graph is called Hamiltonian connected if there exists a Hamiltonian path between any two distinct vertices. In this paper, we will study the Hamiltonian connectivity of rectangular supergrid graphs. Supergrid graphs were first introduced by us and include grid graphs and triangular grid graphs as subgraphs. The Hamiltonian path problem for grid graphs and triangular grid graphs was known to be NP-complete. Recently, we have proved that the Hamiltonian path problem for supergrid graphs is also NP-complete. The Hamiltonian paths on supergrid graphs can be applied to compute the stitching traces of computer sewing machines. Rectangular supergrid graphs form a popular subclass of supergrid graphs, and they have strong structure. In this paper, we provide a constructive proof to show that rectangular supergrid graphs are Hamiltonian connected except one trivial forbidden condition. Based on the constructive proof, we present a linear-time algorithm to construct a longest path between any two given vertices in a rectangular supergrid graph.     

Cubic Bridgeless Graphs and Braces

There are many long-standing open problems on cubic bridgeless graphs, for instance, Jaeger’s directed cycle double cover conjecture. On the other hand, many structural properties of braces have been recently discovered. In this work, we bijectively map the cubic bridgeless graphs to braces which we call the hexagon graphs, and explore the structure of hexagon graphs. We show that hexagon graphs are braces that can be generated from the ladder on 8 vertices using two types of McCuaig’s augmentations. In addition, we present a reformulation of Jaeger’s directed cycle double cover conjecture in the class of hexagon graphs.     

Clustering and domination in perfect graphs

A k-cluster in a graph is an induced subgraph on k vertices which maximizes the number of edges. Both the k-cluster problem and the k-dominating set problem are NP-complete for graphs in general. In this paper we investigate the complexity status of these problems on various sub-classes of perfect graphs. In particular, we examine comparability graphs, chordal graphs, bipartite graphs, split graphs, cographs and κ-trees. For example, it is shown that the k-cluster problem is NP-complete for both bipartite and chordal graphs and the independent k-dominating set problem is NP-complete for bipartite graphs. Furthermore, where the k-cluster problem is polynomial we study the weighted and connected versions as well. Similarly we also look at the minimum k-dominating set problem on families which have polynomial k-dominating set algorithms.     

Obstructions for acyclic local tournament orientation completions

The orientation completion problem for a fixed class of oriented graphs asks whether a given partially oriented graph can be completed to an oriented graph in the class. Orientation completion problems have been studied recently for several classes of oriented graphs, including local tournaments. Local tournaments are intimately related to proper circular-arc graphs and proper interval graphs. In particular, proper interval graphs are precisely those which can be oriented as acyclic local tournaments. In this paper we determine all obstructions for acyclic local tournament orientation completions. These are in a sense minimal partially oriented graphs that cannot be completed to acyclic local tournaments. Our results imply that a polynomial time certifying algorithm exists for the acyclic local tournament orientation completion problem.     

Distance–regular graphs having the M-property

We analyse when the Moore–Penrose inverse of the combinatorial Laplacian of a distance–regular graph is an M-matrix; that is, it has non-positive off-diagonal elements or, equivalently when the Moore–Penrose inverse of the combinatorial Laplacian of a distance–regular graph is also the combinatorial Laplacian of another network. When this occurs we say that the distance–regular graph has the M-property. We prove that only distance–regular graphs with diameter up to three can have the M-property and we give a characterization of the graphs that satisfy the M-property in terms of their intersection array. Moreover, we exhaustively analyse strongly regular graphs having the M-property and we give some families of distance–regular graphs with diameter three that satisfy the M-property. Roughly speaking, we prove that all distance–regular graphs with diameter one; about half of the strongly regular graphs; only some imprimitive distance–regular graphs with diameter three, and no distance–regular graphs with diameter greater than three, have the M-property. In addition, we conjecture that no primitive distance–regular graph with diameter three has the M-property.     

On Universal Equivalence of Partially Commutative Metabelian Lie Algebras

In this paper, we consider partially commutative metabelian Lie algebras whose defining graphs are cycles. We show that such algebras are universally equivalent iff the corresponding cycles have the same length. Moreover, we give an example showing that the class of partially commutative metabelian Lie algebras such that their defining graphs are trees is not separable by universal theory in the class of all partially commutative metabelian Lie algebras.