Strongly Regular Decompositions of the Complete Graph

We study several questions about amorphic association schemes and other strongly regular decompositions of the complete graph. We investigate how two commuting edge-disjoint strongly regular graphs interact. We show that any decomposition of the complete graph into three strongly regular graphs must be an amorphic association scheme. Likewise we show that any decomposition of the complete graph into strongly regular graphs of (negative) Latin square type is an amorphic association scheme. We study strongly regular decompositions of the complete graph consisting of four graphs, and find a primitive counterexample to A.V. Ivanov's conjecture which states that any association scheme consisting of strongly regular graphs only must be amorphic.     

String patterns of leading digits

This paper reviews numerous theoretical results on properties of string sequences generated by leading digits of 2ⁿ and explores their practical implications. The result of Rajagopal et al. on statistical properties of string sequences is discussed. Several recent ideas on the graph-theoretic complexity of string sequences of leading digits are then explored. The application of McCabe's complexity measure to the directed graphs of strings of leading digits is given. In conclusion, uses of these string sequences in different areas of computer science are discussed.     

The Zero-Divisor Graph Associated to a Semigroup

The zero-divisor graph of a commutative semigroup with zero is the graph whose vertices are the nonzero zero-divisors of the semigroup, with two distinct vertices adjacent if the product of the corresponding elements is zero. New criteria to identify zero-divisor graphs are derived using both graph-theoretic and algebraic methods. We find the lowest bound on the number of edges necessary to guarantee a graph is a zero-divisor graph. In addition, the removal or addition of vertices to a zero-divisor graph is investigated by using equivalence relations and quotient sets. We also prove necessary and sufficient conditions for determining when regular graphs and complete graphs with more than two triangles attached are zero-divisor graphs. Lastly, we classify several graph structures that satisfy all known necessary conditions but are not zero-divisor graphs.     

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.     

弦图扩张与最优排序

弦图是一类特殊的完美图,以具有完美消去顺序为特征．由弦图扩张引出一系列序列性组合优化问题,沟通了图论、数值分析及最优排序等领域的若干研究课题．本文将论述我们的一些观点和研究结果．     

图的倍图与补倍图

计算机科学数据库的关系中遇到了可归为倍图或补倍图的参数和哈密顿圈的问题．对简单图C,如果V（D（G））：V（G）∪V（G′）E（D（G））=E（C）∪E（C″）U{vivj′｜vi∈V（G）,Vj′∈V（G′）且vivj∈E（G））那么,称D（C）是C的倍图,如果V（D（G））=V（C）∪V（G′）,E（D（C））：E（C）∪E（G′）∪{vivj′}vi∈V（G）,vj′∈V（G’）and vivj∈（G））,称D（C）是G的补倍图,这里G′是G的拷贝．本文研究了D（G）和D的色数,边色数,欧拉性,哈密顿性和提出了D（G） 的边色数是D（G）的最大度等公开问题．     

Lock-Gain Based Graph Partitioning

We propose a new heuristic for the graph partitioning problem. Based on the traditional iterative improvement framework, the heuristic uses a new type of gain in selecting vertices to move between partitions. The new type of gain provides a good explanation for the performance difference of tie-breaking strategies in KL-based iterative improvement graph partitioning algorithms. The new heuristic performed excellently. Theoretical arguments supporting its efficacy are also provided. As the proposed heuristic is considered a good candidate for local optimization engines in metaheuristics, we combined it with a genetic algorithm as a sample case and obtained a surprising result that even the average results over 1,000 runs equalled the best known for most graphs.     

An Algebraic Formulation of the Graph Reconstruction Conjecture

The graph reconstruction conjecture asserts that every finite simple graph on at least three vertices can be reconstructed up to isomorphism from its deck—the collection of its vertex‐deleted subgraphs. Kocay's Lemma is an important tool in graph reconstruction. Roughly speaking, given the deck of a graph G and any finite sequence of graphs, it gives a linear constraint that every reconstruction of G must satisfy. Let be the number of distinct (mutually nonisomorphic) graphs on n vertices, and let be the number of distinct decks that can be constructed from these graphs. Then the difference measures how many graphs cannot be reconstructed from their decks. In particular, the graph reconstruction conjecture is true for n‐vertex graphs if and only if . We give a framework based on Kocay's lemma to study this discrepancy. We prove that if M is a matrix of covering numbers of graphs by sequences of graphs, then . In particular, all n‐vertex graphs are reconstructible if one such matrix has rank . To complement this result, we prove that it is possible to choose a family of sequences of graphs such that the corresponding matrix M of covering numbers satisfies .     

Petersen图的点传递正则覆盖图

运用基图自同构能被提升的线性准则 ,对满足 :1覆叠变换群 K =Znp,2覆盖图的保簇变换群是点传递的 Petersen图的连通正则覆盖图进行了完全分类 .这种图共有 1 2种类型 .     

图带宽的若干刻划

本文研究图的带宽的若干等价刻划以及相关的理论结果。     

Graph labeling and radio channel assignment

The vertex-labeling of graphs with nonnegative integers provides a natural setting in which to study problems of radio channel assignment. Vertices correspond to transmitter locations and their labels to radio channels. As a model for the way in which interference is avoided in real radio systems, each pair of vertices has, depending on their separation, a constraint on the difference between the labels that can be assigned. We consider the question of finding labelings of minimum span, given a graph and a set of constraints. The focus is on the infinite triangular lattice, infinite square lattice, and infinite line lattice, and optimal labelings for up to three levels of constraint are obtained. We highlight how accepted practice can lead to suboptimal channel assignments. © 1998 John Wiley & Sons, Inc. J Graph Theory 29: 263–283, 1998     

自对偶图的充要条件

给出自对偶图的充要条件,并利用此充要条件,能构造出所有自对偶图.     

Graph unique-maximum and conflict-free colorings

We investigate the relationship between two kinds of vertex colorings of graphs: unique-maximum colorings and conflict-free colorings. In a unique-maximum coloring, the colors are ordered, and in every path of the graph the maximum color appears only once. In a conflict-free coloring, in every path of the graph there is a color that appears only once. We also study computational complexity aspects of conflict-free colorings and prove a completeness result. Finally, we improve lower bounds for those chromatic numbers of the grid graph.     

关于乘积图的二维带宽问题

给出一般乘积图的二维带宽的界，并解决一类乘积图的二维带宽问题．最后给出完全ｋ部图的二维带宽。     

关于图P_n~3优美性的研究

在n个顶点的路Pn上,当且仅当两点的距离为3时增加一条边,所得的图称为P3n,本文给出了图P3n(n≥4)的优美标号,从而证明了P3n都是优美图.     

On the Differential Polynomial of a Graph

We introduce the differential polynomial of a graph. The differential polynomial of a graph G of order n is the polynomial B(G; x) :=∑?(G)k=-nB_k(G) x~(n+k), where B_k(G) denotes the number of vertex subsets of G with differential equal to k. We state some properties of B(G;x) and its coefficients.In particular, we compute the differential polynomial for complete, empty, path, cycle, wheel and double star graphs. We also establish some relationships between B(G; x) and the differential polynomials of graphs which result by removing, adding, and subdividing an edge from G.     

Graph layering by promotion of nodes

This work contributes to the wide research area of visualization of hierarchical graphs. We present a new polynomial-time heuristic which can be integrated into the Sugiyama method for drawing hierarchical graphs. Our heuristic, which we call Promote Layering (PL), is applied to the output of the layering phase of the Sugiyama method. PL is a simple and easy to implement algorithm which decreases the number of so-called dummy (or virtual) nodes in a layered directed acyclic graph. In particular, we propose applying PL after the longest-path layering algorithm and we present an extensive empirical evaluation of this layering technique.