Threshold tolerance graphs

In this paper, we introduce a class of graphs that generalize threshold graphs by introducing threshold tolerances. Several characterizations of these graphs are presented, one of which leads to a polynomial-time recognition algorithm. It is also shown that the complements of these graphs contain interval graphs and threshold graphs, and are contained in the subclass of chordal graphs called strongly chordal graphs, and in the class of interval tolerance graphs.     

灯笼图的奇优美标号

提出了灯笼图、多向灯笼图、复杂灯笼图,研究了它们的奇优美性,证明灯笼图是二分奇优美图、超级边魔幻图和超级反魔幻图.     

General results on tolerance intersection graphs

In this paper, general results are presented that are related to ?-tolerance intersection graphs previously defined by Jacobson, McMorris, and Mulder. For example, it is shown that all graphs are ?-tolerance intersection graphs for all ?, yet for “nice” ?, almost no graphs are ?-tolerance interval graphs. Additional results about representation of trees are given.     

Combinatorially homogeneous graphs

Gardiner classified ultrahomogeneous graphs and posed the problem of defining “combinatorial homogeneity”. Later, Ronse proved that homogeneous graphs are ultrahomogeneous by classifying such graphs. In this paper, we give a direct proof that (suitably defined) combinatorially homogeneous graphs are ultrahomogeneous. Also, we clasify combinatorially C-homogeneous graphs.     

kpm阶2-弧传递图

2-弧传递图是对称图类的一个重要的子类,而拟本原和双拟本原的2-弧传递图在2-弧传递图的研究中具有最基本的意义．文中对阶为kp^m（k,p是素数,k≠p,m≥2是整数)的基本2-孤传递图进行了研究。获得了下列结果：(1)kp^m阶G-拟本原的2-弧传递图是几乎单的．(2)对2p^m阶和2^mk阶双拟本原的2-弧传递图的分类进行了刻划,确定了其自同构群的基柱．     

Claw-free graphs with strongly perfect complements. Fractional and integral version, Part II: Nontrivial strip-structures

Strongly perfect graphs have been studied by several authors (e.g., Berge and Duchet (1984) [1], Ravindra (1984) [7] and Wang (2006) [8]). In a series of two papers, the current paper being the second one, we investigate a fractional relaxation of strong perfection. Motivated by a wireless networking problem, we consider claw-free graphs that are fractionally strongly perfect in the complement. We obtain a forbidden induced subgraph characterization and display graph-theoretic properties of such graphs. It turns out that the forbidden induced subgraphs that characterize claw-free graphs that are fractionally strongly perfect in the complement are precisely the cycle of length 6, all cycles of length at least 8, four particular graphs, and a collection of graphs that are constructed by taking two graphs, each a copy of one of three particular graphs, and joining them in a certain way by a path of arbitrary length. Wang (2006) [8] gave a characterization of strongly perfect claw-free graphs. As a corollary of the results in this paper, we obtain a characterization of claw-free graphs whose complements are strongly perfect.     

Claw-free graphs with strongly perfect complements. Fractional and integral version. Part I. Basic graphs

Strongly perfect graphs have been studied by several authors (e.g. Berge and Duchet (1984) [1], Ravindra (1984) [12] and Wang (2006) [14]). In a series of two papers, the current paper being the first one, we investigate a fractional relaxation of strong perfection. Motivated by a wireless networking problem, we consider claw-free graphs that are fractionally strongly perfect in the complement. We obtain a forbidden induced subgraph characterization and display graph-theoretic properties of such graphs. It turns out that the forbidden induced subgraphs that characterize claw-free graphs that are fractionally strongly perfect in the complement are precisely the cycle of length 6, all cycles of length at least 8, four particular graphs, and a collection of graphs that are constructed by taking two graphs, each a copy of one of three particular graphs, and joining them in a certain way by a path of arbitrary length. Wang (2006) [14] gave a characterization of strongly perfect claw-free graphs. As a corollary of the results in this paper, we obtain a characterization of claw-free graphs whose complements are strongly perfect.     

On the Number of Non-Hamiltonian Graphs

In this paper, maximal non-Hamiltonian graphs ( MNH graphs), i.e., non-Hamiltonian graphs such that the addition of any new edge violates their property of being non-Hamiltonian are studied. It is shown that the study of MNH graphs can be reduced to the study of the so-called simplified MNH graphs. Restrictions on the structure of maximal cliques of simplified MNH graphs are obtained, the orders and the number of such graphs are estimated.     

Which distance-hereditary graphs are cover–incomparability graphs?

In this paper we deal with cover–incomparability graphs of posets, or briefly C–I graphs. These are graphs derived from posets as the edge-union of their cover graph and their incomparability graph. We answer two recently posed open questions. Which distance-hereditary graphs are C–I graphs? Which Ptolemaic (i.e. chordal distance-hereditary) graphs are C–I graphs? It follows that C–I graphs can be recognized efficiently in the class of all distance-hereditary graph whereas recognizing C–I graphs in general is known to be NP-complete.     

Locally Transitive Graphs Admitting a Group with Cyclic Sylow Subgroups

All graphs are finite simple undirected and of no isolated vertices in this paper. Using the theory of coset graphs and permutation groups, it is completed that a classification of locally transitive graphs admitting a non-Abelian group with cyclic Sylow subgroups. They are either the union of the family of arc-transitive graphs, or the union of the family of bipartite edge-transitive graphs.     

𝒢-constructibility of planar graphs

In this paper, the concept of the ??-constructibility of graphs is introduced and investigated with particular reference to planar graphs. It is conjectured that the planar graphs are minimally N-constructible, where N is a finite set of graphs and an infinite set ?? is obtained such that the planar graphs are also minimally ??-constructible. Finally, some properties of the set of all N-constructible graphs are discussed and compared with the corresponding properties of planar 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.     

关于双顶边星图的优美性

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

On the Complexity of Cover-Incomparability Graphs of Posets

In this paper we show that the recognition problem for C-I graphs of posets is NP-complete. On the other hand, we prove that induced subgraphs of C-I graphs are exactly complements of comparability graphs, and hence the recognition problem for induced subgraphs of C-I graphs of posets is polynomial.     

On bounds for the index of double nested graphs

The index of a simple graph is the largest eigenvalue of its adjacency matrix. It is well-known that in the set of all connected graphs with fixed order and size the graphs with maximal index are nested split graphs. It was recently observed that double nested graphs assume the same role if we restrict ourselves to bipartite graphs. In this paper we provide some bounds (lower and upper) for the index of double nested graphs. Some computational results are also included.     

Graph structural properties of non-Yutsis graphs allowing fast recognition

Yutsis graphs are connected simple graphs which can be partitioned into two vertex-induced trees. Cubic Yutsis graphs were introduced by Jaeger as cubic dual Hamiltonian graphs, and these are our main focus.Cubic Yutsis graphs also appear in the context of the quantum theory of angular momenta, where they are used to generate summation formulae for general recoupling coefficients. Large Yutsis graphs are of interest for benchmarking algorithms which generate these formulae.In an earlier paper we showed that the decision problem of whether a given cubic graph is Yutsis is NP-complete. We also described a heuristic that was tested on graphs with up to 300,000 vertices and found Yutsis decompositions for all large Yutsis graphs very quickly.In contrast, no fast technique was known by which a significant fraction of bridgeless non-Yutsis cubic graphs could be shown to be non-Yutsis. One of the contributions of this article is to describe some structural impediments to Yutsisness. We also provide experimental evidence that almost all non-Yutsis cubic graphs can be rapidly shown to be non-Yutsis by applying a heuristic based on some of these criteria. Combined with the algorithm described in the earlier paper this gives an algorithm that, according to experimental evidence, runs efficiently on practically every large random cubic graph and can decide on whether the graph is Yutsis or not.The second contribution of this article is a set of construction techniques for non-Yutsis graphs implying, for example, the existence of 3-connected non-Yutsis cubic graphs of arbitrary girth and with few non-trivial 3-cuts.     

分子图的Zagreb拓扑指标的逆问题

研究了化学分子图的Zagreb指标的逆问题，解决了对于给定的怎样的数存在分子图，其Zagreb指标值等于该数的问题，对n个顶点m条边的简单连通图，给出了其具有最小Zagreb指标值的充分必要条件，并给出了其具有最大Zagreb指标值的必要条件，为利用计算机搜索具有给定Zagreb指标值的所有分子图界定了顶点数和边数的范围，从而提高了计算机搜索的效率，这在组合化学中具有重要的意义。     

Posets with interval upper bound graphs

Competition graphs of transitive acyclic digraphs are strict upper bound graphs. This paper characterizes those posets, which can be considered transitive acyclic digraphs, which have upper bound graphs that are interval graphs. The results proved here may shed some light on the open question of those digraphs which have interval competition graphs.This material is taken from Chapter 3 of my (maiden name Diny) PhD Dissertation.     

Approximating the minimum clique cover and other hard problems in subtree filament graphs

Subtree filament graphs are the intersection graphs of subtree filaments in a tree. This class of graphs contains subtree overlap graphs, interval filament graphs, chordal graphs, circle graphs, circular-arc graphs, cocomparability graphs, and polygon-circle graphs. In this paper we show that, for circle graphs, the clique cover problem is NP-complete and the h-clique cover problem for fixed h is solvable in polynomial time. We then present a general scheme for developing approximation algorithms for subtree filament graphs, and give approximation algorithms developed from the scheme for the following problems which are NP-complete on circle graphs and therefore on subtree filament graphs: clique cover, vertex colouring, maximum k-colourable subgraph, and maximum h-coverable subgraph.     

Cayley graphs as classifiers for data mining: The influence of asymmetries

The endomorphism monoids of graphs have been actively investigated. They are convenient tools expressing asymmetries of the graphs. One of the most important classes of graphs considered in this framework is that of Cayley graphs. Our paper proposes a new method of using Cayley graphs for classification of data. We give a survey of recent results devoted to the Cayley graphs also involving their endomorphism monoids.