On the Ascending Subgraph Decomposition Problem

§１．　ＩｎｔｒｏｄｕｃｔｉｏｎＩｎｐａｐｅｒ［１］,Ａｌａｖｉａｎｄｏｔｈｅｒｓｄｅｆｉｎｅｄｔｈｅｃｏｎｃｅｐｔｏｆａｓｃｅｎｄｉｎｇｓｕｂｇｒａｐｈｄｅｃｏｍｐｏｓｉｔｉｏｎ：Ｄｅｆｉｎｉｔｉｏｎ　ＬｅｔＧｂｅａｇｒａｐｈｏｆｐｏｓｉｔｉｖｅｓｉｚｅｑ,ａｎｄｌｅｔｎｂｅｔｈａｔｐｏｓｉｔｉｖｅｉｎｔｅｇｅｒｆｏｒｗｈｉｃｈｎ＋１２ｑ＜ｎ＋２２．ＴｈｅｎＧｉｓｓａｉｄｔｏｈａｖｅａｎａｓｃｅｎｄｉｎｇｓｕｂｇｒａｐｈｄｅｃｏｍｐｏｓｉｔｉｏｎ（ＡＳＤ）ｉｆＧｃａｎｂｅｄｅｃｏｍｐｏｓｅｄ…     

图K_nH_((5n/2)-4)的升分解

Ａｌａｖｉ等人给出了图的升分解的概念并猜测任何一个有正数条边的图都可以升分解．Ｆａｕｄｒｅｅ等１９８７年证明了当完全图Ｋｎ的子图Ｈ至多有ｎ—１条边时，Ｋｎ－Ｈ可以升分解．马克杰等１９９７年证明了当Ｈ至多含有ｎ条边时，Ｋｎ－Ｈ可以升分解．作者１９９９年证明了当Ｈ的边数小于３ｎ／２时，Ｋｎ－Ｈ可以升分解．本文将证明当Ｈ的边数小于（５ｎ／２）－４时Ｋｎ－Ｈ有升分解．     

关于图的一种新分解

Alavi等人在[1]中定义了图的一种新分解,即升分解,并提出猜想:     

Parity and disparity subgraphs

A parity subgraph of a graph is a spanning subgraph such that the degrees of each vertex have the same parity in both the subgraph and the original graph. Known results include that every graph has an odd number of minimal parity subgraphs. Define a disparity subgraph to be a spanning subgraph such that each vertex has degrees of opposite parities in the subgraph and the original graph. (Only graphs with all even-order components can have disparity subgraphs). Every even-order spanning tree contains both a unique parity subgraph and a unique disparity subgraph. Moreover, every minimal disparity subgraph is shown to be paired by sharing a spanning tree with an odd number of minimal parity subgraphs, and every minimal parity subgraph is similarly paired with either one or an even number of minimal disparity subgraphs.     

Packing strong subgraph in digraphs

In this paper, we study two types of strong subgraph packing problems in digraphs, including internally disjoint strong subgraph packing problem and arc-disjoint strong subgraph packing problem. These problems can be viewed as generalizations of the famous Steiner tree packing problem and are closely related to the strong arc decomposition problem. We first prove the NP-completeness for the internally disjoint strong subgraph packing problem restricted to symmetric digraphs and Eulerian digraphs. Then we get inapproximability results for the arc-disjoint strong subgraph packing problem and the internally disjoint strong subgraph packing problem. Finally we study the arc-disjoint strong subgraph packing problem restricted to digraph compositions and obtain some algorithmic results by utilizing the structural properties.     

以子图为根的k距局部子图的可重构性

本文定义了图中以某个图为根的k距局部子图，证明了图中同构于上述 k距局部子图的子图的数目是可重构的，从而给出了一个新结果并推广了文献^[5]中的定理。     

Ascending Subgraph Decompositions in Oriented Complete Balanced Tripartite Graphs

In 1987, Alavi, Boals, Chartrand, Erdös, and Oellermann conjectured that all graphs have an ascending subgraph decomposition (ASD). Though different classes of graphs have been shown to have an ASD, the conjecture remains open. In this paper we investigate the similar problem for digraphs. In particular, we will show that any orientation of a compete balanced tripartite graph has an ASD.     

图模式挖掘中的子图同构算法

图模式挖掘问题在Web挖掘、生物信息学、社会关系等众多领域有广泛的应用,它涉及到子图的搜索以及子图的同构问题.这两个问题都具有相当高的计算复杂度,现有的子图同构问题大多采用最小编码算法,但对无标签图特别是对无标签无向图,该算法效率较底,从而子图的同构成为图模式挖掘问题的一个瓶颈.针对无标签图,以代数理论为基础,分别利用度序列和特征值构造了两种子图同构算法,用于对有向图和无向图的同构判别.最后对2个真实生物网络进行了仿真实验,结果表明,算法的效率优于现有算法.     

Bounded degree acyclic decompositions of digraphs

An acyclic decomposition of a digraph is a partition of the edges into acyclic subgraphs. Trivially every digraph has an acyclic decomposition into two subgraphs. It is proved that for every integer s2 every digraph has an acyclic decomposition into s subgraphs such that in each subgraph the outdegree of each vertex v is at most . For all digraphs this degree bound is optimal.     

Two forbidden induced subgraphs and well-quasi-ordering

It is known that a class of graphs defined by a single forbidden induced subgraph G is well-quasi-ordered by the induced subgraph relation if and only if G is an induced subgraph of P₄. However, very little is known about well-quasi-ordered classes of graphs defined by more than one forbidden induced subgraph. We conjecture that for any natural number k, there are finitely many minimal classes of graphs defined by k forbidden induced subgraphs which are not well-quasi-ordered by the induced subgraph relation and prove the conjecture for k=2. We explicitly reveal many of the minimal classes defined by two forbidden induced subgraphs which are not well-quasi-ordered and many of those which are well-quasi-ordered by the induced subgraph relation.     

Odd subgraphs and matchings

Let G be a graph and f : V(G)→{1,3,5,…}. Then a subgraph H of G is called a (1,f)-odd subgraph if deg_H(x){1,3,…,f(x)} for all xV(H). If f(x)=1 for all xV(G), then a (1,f)-odd subgraph is nothing but a matching. A (1,f)-odd subgraph H of G is said to be maximum if G has no (1,f)-odd subgraph K such that |K|>|H|. We show that (1,f)-odd subgraphs have some properties similar to those of matchings, in particular, we give a formula for the order of a maximum (1,f)-odd subgraph, which is similar to that for the order of a maximum matching.     

Note on 2-edge-colorings of complete graphs with small monochromatic k-connected subgraphs

Bollob′as and Gy′arf′as conjectured that for n4(k-1) every 2-edge-coloring of Kn contains a monochromatic k-connected subgraph with at least n-2k+2 verticesLiu, et alproved that the conjecture holds when n≥13k-15In this note, we characterize all the2-edge-colorings of Kn where each monochromatic k-connected subgraph has at most n-2k+2 vertices for n≥13k-15.     

On canonical antichains

An antichain A of a well-founded quasi-order Q is canonical if for every ideal F of Q, F has an infinite antichain if and only if F∩A is infinite. In this paper we characterize the obstructions to having a canonical antichain. As an application we show that, under the induced subgraph relation, the class of finite graphs does not have a canonical antichain. In contrast, this class does have a canonical antichain with respect to the subgraph relation.     

The connected partition lattice of a graph and the reconstruction conjecture

Previously we showed that many invariants of a graph can be computed from its abstract induced subgraph poset, which is the isomorphism class of the induced subgraph poset, suitably weighted by subgraph counting numbers. In this paper, we study the abstract bond lattice of a graph, which is the isomorphism class of the lattice of distinct unlabelled connected partitions of a graph, suitably weighted by subgraph counting numbers. We show that these two abstract posets can be constructed from each other except in a few trivial cases. The constructions rely on certain generalisations of a lemma of Kocay in graph reconstruction theory to abstract induced subgraph posets. As a corollary, trees are reconstructible from their abstract bond lattice. We show that the chromatic symmetric function and the symmetric Tutte polynomial of a graph can be computed from its abstract induced subgraph poset. Stanley has asked if every tree is determined up to isomorphism by its chromatic symmetric function. We prove a counting lemma, and indicate future directions for a study of Stanley's question.     

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.     

qq-2-树整子图的色性

研究具有与qq-2-树整子图有相同色多项式的图的结构,利用分类法,得到当q至少为2至多为5时qq-2-树整子图的色性.     

关于q-树二次整子图和n阶加点q-树色多项式的注记

在这篇文章中我们成功地仅用色多项式表征了最小度不等于q-3的q-树的二次整子图和n阶加点q-树,即当图的最小度δ(G)≠q-3时,n阶图G具有色多项式P(G;λ)=λ(λ-1)…(λ-q+2)(λ-q+1)~3(λ-q)~(n-q-2), n≥q+2,当且仅当G是n阶q-树的二次整子图或n阶加点q-树.     

On 2-Detour Subgraphs of the Hypercube

A spanning subgraph H of a graph G is a 2-detour subgraph of G if for each x, y ∈ V(G), d _H (x, y) ≤ d _G (x, y) + 2. We prove a conjecture of Erdős, Hamburger, Pippert, and Weakley by showing that for some positive constant c and every n, each 2-detour subgraph of the n-dimensional hypercube Q _n has at least clog₂ n · 2 ⁿ edges. József Balogh: Research supported in part by NSF grants DMS-0302804, DMS-0603769 and DMS-0600303, UIUC Campus Reseach Board #06139 and #07048, and OTKA 049398. Alexandr Kostochka: Research supported in part by NSF grants DMS-0400498 and DMS-0650784, and grant 06-01-00694 of the Russian Foundation for Basic Research.     

A characterization of level planar graphs

We present a characterization of level planar graphs in terms of minimal forbidden subgraphs called minimal level non-planar (MLNP) subgraph patterns. We show that an MLNP subgraph pattern is completely characterized by either a tree, a level non-planar cycle or a level planar cycle with certain path augmentations.     

Heuristics for the Maximum Outerplanar Subgraph Problem

Determining the maximum outerplanar subgraph of a given graph is known to be an NP-complete problem. In the literature there are no earlier experiment on approximating the maximum outerplanar subgraph problem. In this paper we compare solution quality and running times of different heuristics for finding maximum outerplanar subgraphs. We compare a greedy heuristic against a triangular cactus heuristic and its greedy variation. We also use the solutions from the greedy heuristics as initial solutions for a simulated annealing algorithm.The main experimental result is that simulated annealing with initial solution taken from the greedy triangular cactus heuristic yields the best known approximations for the maximum outerplanar subgraph problem.Work funded by the Tampere Graduate School in Information Science and Engineering (TISE) and supported by the Academy of Finland (Project 51528).