整图的构造

In this paper, some new classes of integral graphs are given in two new ways. It is proved that the problem of finding such integral graphs is equivalent to the problem of solving diophantine equations. Some classes are infinite. The discovery of these classes is a new contribution to the search of such integral graphs.     

New types of integral sum graphs

Harary (Discrete Math. 124(1–3) (1994) 99) introduced the intergral sum graphs, and proved that the path P_n and matching mK₂ are integer sum graphs, and offered some conjectures. In this paper we enlarge the types of integral sum graphs. We prove that some caterpillars and mP_n are integral sum graphs and some conjectures of Harary are wrong.     

Distance Integral Complete Multipartite Graphs with s=5, 6

Let D(G) = (dij )n×n denote the distance matrix of a connected graph G with order n, where dij is equal to the distance between vertices vi and vj in G. A graph is called distance integral if all eigenvalues of its distance matrix are integers. In 2014, Yang and Wang gave a su?cient and necessary condition for complete r-partite graphs Kp1,p2,··· ,pr =Ka1·p1,a2·p2,··· ,as···ps to be distance integral and obtained such distance integral graphs with s = 1, 2, 3, 4. However distance integral complete multipartite graphs Ka1·p1,a2·p2,··· ,as·ps with s>4 have not been found. In this paper, we find and construct some infinite classes of these distance integral graphs Ka1·p1,a2·p2,··· ,as·ps with s = 5, 6. The problem of the existence of such distance integral graphs Ka1·p1,a2·p2,··· ,as·ps with arbitrarily large number s remains open.     

On the Laplacian integral tricyclic graphs

A graph is called Laplacian integral if all its Laplacian eigenvalues are integers. In this paper, we give an edge subdividing theorem for Laplacian eigenvalues of a graph (Theorem 2.1) and characterize a class of k-cyclic graphs whose algebraic connectivity is less than one. Using these results, we determine all the Laplacian integral tricyclic graphs. Furthermore, we show that all the Laplacian integral tricyclic graphs are determined by their Laplacian spectra.     

Integral circulant graphs

In this note we characterize integral graphs among circulant graphs. It is conjectured that there are exactly 2^τ(n)-1 non-isomorphic integral circulant graphs on n vertices, where τ(n) is the number of divisors of n.     

On integral sum graphs

A graph G is said to be an integral sum graph if its nodes can be given a labeling f with distinct integers, so that for any two distinct nodes u and v of G, uv is an edge of G if and only if f(u)+f(v)=f(w) for some node w in G. A node of G is called a saturated node if it is adjacent to every other node of G. We show that any integral sum graph which is not K₃ has at most two saturated nodes. We determine the structure for all integral sum graphs with exactly two saturated nodes, and give an upper bound for the number of edges of a connected integral sum graph with no saturated nodes. We introduce a method of identification on constructing new connected integral sum graphs from given integral sum graphs with a saturated node. Moreover, we show that every graph is an induced subgraph of a connected integral sum graph. Miscellaneous related results are also presented.     

Split non-threshold Laplacian integral graphs

The aim of this article is to answer a question posed by Merris in European Journal of Combinatorics, 24 (2003) pp. 413 ? 430, about the possibility of finding split non-threshold graphs that are Laplacian integral, i.e. graphs for which the eigenvalues of the corresponding Laplacian matrix are integers. Using Kronecker products, balanced incomplete block designs, and solutions to certain Diophantine equations, we show how to build infinite families of these graphs.     

用超广义线图构造整谱图

线图在图的谱理论研究中起着重要的作用.在本文中,通过研究超广义线图成为整谱图的充分条件,获得了一种全新的构造新的整 谱图的方法,运用这种方法,可以构造出无穷多个新的整谱图.     

Infinitely many pairs of cospectral integral regular graphs

A graph G is called integral if all the eigenvalues of the adjacency matrix A(G) of G are integers. In this paper, the graphs G ₄(a, b) and G ₅(a, b) with 2a+6b vertices are defined. We give their characteristic polynomials from matrix theory and prove that the (n+2)-regular graphs G ₄(n, n+2) and G ₅(n, n+2) are a pair of non-isomorphic connected cospectral integral regular graphs for any positive integer n.     

Oriented bipartite graphs and the Goldbach graph

In this paper, we study oriented bipartite graphs. In particular, we introduce “bitransitive” graphs. Several characterizations of bitransitive bitournaments are obtained. We show that bitransitive bitounaments are equivalent to acyclic bitournaments. As applications, we characterize acyclic bitournaments with Hamiltonian paths, determine the number of non-isomorphic acyclic bitournaments of a given order, and solve the graph-isomorphism problem in linear time for acyclic bitournaments. Next, we prove the well-known Caccetta-Häggkvist Conjecture for oriented bipartite graphs in some cases for which it is unsolved, in general, for oriented graphs. We also introduce the concept of undirected as well as oriented “odd-even” graphs. We characterize bipartite graphs and acyclic oriented bipartite graphs in terms of them. In fact, we show that any bipartite graph (acyclic oriented bipartite graph) can be represented by some odd-even graph (oriented odd-even graph). We obtain some conditions for connectedness of odd-even graphs. This study of odd-even graphs and their connectedness is motivated by a special family of odd-even graphs which we call “Goldbach graphs”. We show that the famous Goldbach's conjecture is equivalent to the connectedness of Goldbach graphs. Several other number theoretic conjectures (e.g., the twin prime conjecture) are related to various parameters of Goldbach graphs, motivating us to study the nature of vertex-degrees and independent sets of these graphs. Finally, we observe Hamiltonian properties of some odd-even graphs related to Goldbach graphs for a small number of vertices.     

Equistable graphs, general partition graphs, triangle graphs, and graph products

In this paper we examine the connections between equistable graphs, general partition graphs and triangle graphs. While every general partition graph is equistable and every equistable graph is a triangle graph, not every triangle graph is equistable, and a conjecture due to Jim Orlin states that every equistable graph is a general partition graph. The conjecture holds within the class of chordal graphs; if true in general, it would provide a combinatorial characterization of equistable graphs.Exploiting the combinatorial features of triangle graphs and general partition graphs, we verify Orlin’s conjecture for several graph classes, including AT-free graphs and various product graphs. More specifically, we obtain a complete characterization of the equistable graphs that are non-prime with respect to the Cartesian or the tensor product, and provide some necessary and sufficient conditions for the equistability of strong, lexicographic and deleted lexicographic products. We also show that the general partition graphs are not closed under the strong product, answering a question by McAvaney et al.     

关于一类边裂图的k-边幻性

通常没有有效的方法判别一般图G的k-边幻性.本文采用分析方法,讨论了一类非均匀边裂图SPE(Cn,h)的边幻性和k-边幻性,得到一些新的结果.     

Introducing subclasses of basic chordal graphs

Basic chordal graphs arose when comparing clique trees of chordal graphs and compatible trees of dually chordal graphs. They were defined as those chordal graphs whose clique trees are exactly the compatible trees of its clique graph.In this work, we consider some subclasses of basic chordal graphs, like hereditary basic chordal graphs, basic DV and basic RDV graphs, we characterize them and we find some other properties they have, mostly involving clique graphs.     

On the Calculation of Multiplicities for P-Polynomial C-Algebras

An alternative rational function, with polynomial components of smaller degree, is constructed to compute multiplicities for a P-polynomial C-algebra whose generating tri-diagonal matrix has a set of repeated column entries. As a consequence, some upper bounds are derived for the diameter of the algebra. The bound in the case of an integral table algebra generalizes a well known result of Bannai and Ito for distance-regular graphs.     

有限素数度弧正则图

如果一个图的全自同构群在其弧集上正则,则称此图为弧正则图.本文刻画素数度的立方自由阶弧正则图,证明任何素数度2倍奇立方自由阶弧正则图都是正规或二部正规Cayley图,且不存在任意素数度4倍奇立方自由阶的弧正则图,推广了一些已知的结果,得到阶为8倍奇平方自由阶素数度弧正则图的分类,并发现新的弧正则图类.此外,基于所得的结果,我们提出一个猜想和有待后续研究的一些问题.     

Balanced Cayley graphs and balanced planar graphs

A balanced graph is a bipartite graph with no induced circuit of length . These graphs arise in integer linear programming. We focus on graph-algebraic properties of balanced graphs to prove a complete classification of balanced Cayley graphs on abelian groups. Moreover, in this paper, we prove that there is no cubic balanced planar graph. Finally, some remarkable conjectures for balanced regular graphs are also presented. The graphs in this paper are simple.     

关于紧图和超紧图的几个结果

给出了一些 新的紧图,并对 不是超紧的紧图 作了一些讨论     

图的联结数与分数n-边(点)可消去图

讨论了图的联结数bind(G)与分数n-边(点)可消去图之间的关系,给出了一个图是分数n-边(点)可消去图的若干充分条件.     

New constructions of hypohamiltonian and hypotraceable graphs

A graph G is hypohamiltonian/hypotraceable if it is not hamiltonian/traceable, but all vertex‐deleted subgraphs of G are hamiltonian/traceable. All known hypotraceable graphs are constructed using hypohamiltonian graphs; here we present a construction that uses so‐called almost hypohamiltonian graphs (nonhamiltonian graphs, whose vertex‐deleted subgraphs are hamiltonian with exactly one exception, see [15]). This construction is an extension of a method of Thomassen [11]. As an application, we construct a planar hypotraceable graph of order 138, improving the best‐known bound of 154 [8]. We also prove a structural type theorem showing that hypotraceable graphs possessing some connectivity properties are all built using either Thomassen's or our method. We also prove that if G is a Grinbergian graph without a triangular region, then G is not maximal nonhamiltonian and using the proof method we construct a hypohamiltonian graph of order 36 with crossing number 1, improving the best‐known bound of 46 [14].     

Symmetry properties of Cayley graphs of small valencies on the alternating group A_5

The normality of symmetry property of Cayley graphs of valencies 3 and 4 on the alternating group A5 is studied. We prove that all but four such graphs are normal; that A5 is not 5-CI. A complete classification of all arc-transitive Cayley graphs on A5 of valencies 3 and 4 as well as some examples of trivalent and tetravalent GRRs of A5 is given.