Remarks on Q-integral complete multipartite graphs

A graph is Q-integral if the spectrum of its signless Laplacian matrix consists entirely of integers. In their study of Q-integral complete multipartite graphs, [Zhao et al., Q-integral complete r-partite graphs, Linear Algebra Appl. 438 (2013) 1067–1077] posed two questions on the existence of such graphs. We resolve these questions and present some further results characterizing particular classes of Q-integral complete multipartite graphs.     

Laplacian spectral characterization of disjoint union of paths and cycles

The Laplacian spectrum of a graph consists of the eigenvalues (together with multiplicities) of the Laplacian matrix. In this article we determine, among the graphs consisting of disjoint unions of paths and cycles, those ones which are determined by the Laplacian spectrum. For the graphs, which are not determined by the Laplacian spectrum, we give the corresponding cospectral non-isomorphic graphs.     

On the spectral characterization of the union of complete multipartite graph and some isolated vertices

A graph is said to be determined by its adjacency spectrum (DS for short) if there is no other non-isomorphic graph with the same spectrum. In this paper, we focus our attention on the spectral characterization of the union of complete multipartite graph and some isolated vertices, and all its cospectral graphs are obtained. By the results, some complete multipartite graphs determined by their adjacency spectrum are also given. This extends several previous results of spectral characterization related to the complete multipartite graphs.     

Spectral Characterizations of Some Distance-Regular Graphs

When can one see from the spectrum of a graph whether it is distance-regular or not? We give some new results for when this is the case. As a consequence we find (among others) that the following distance-regular graphs are uniquely determined by their spectrum: The collinearity graphs of the generalized octagons of order (2,1), (3,1) and (4,1), the Biggs-Smith graph, the M ₂₂ graph, and the coset graphs of the doubly truncated binary Golay code and the extended ternary Golay code.     

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.     

一个关于图谱的受控定理的推广

本文将一个关于两个不交国的单点粘合的图的LPlaCe谱的受控定理推广到了两个国的多点粘合何形；同时证明了相同的结果对目的Q一回也成立。     

On some properties of o-degeneracy graphs

Degenerate optima in linear programming problems lead in a canonical way to so-called o-degeneracy graphs as subgraphs of degeneracy graphs induced by the set of optimal bases. Fundamental questions about the structure of o-degeneracy graphs suggest the closer inspection of some properties of these graphs, such as, for example, the connectivity and the complexity. Finally, some open questions are pointed out.     

基于拉普拉斯谱确定的两类树

设图G是简单连通图.如果任何一个与图G关于拉普拉斯矩阵同谱的图,都与图G同构,称图G可由其拉普拉斯谱确定.定义了树Y_n和树F(2,n,1)两类特殊结构的树.利用同谱图线图的特点,证明了树Y_n和树F(2,n,1)可由其拉普拉斯谱确定.     

The spectral characterization of graphs of index less than 2 with no path as a component

A graph is said to be determined by the adjacency and Laplacian spectrum (or to be a DS graph, for short) if there is no other non-isomorphic graph with the same adjacency and Laplacian spectrum, respectively. It is known that connected graphs of index less than 2 are determined by their adjacency spectrum. In this paper, we focus on the problem of characterization of DS graphs of index less than 2. First, we give various infinite families of cospectral graphs with respect to the adjacency matrix. Subsequently, the results will be used to characterize all DS graphs (with respect to the adjacency matrix) of index less than 2 with no path as a component. Moreover, we show that most of these graphs are DS with respect to the Laplacian matrix.     

Forbidden induced subgraph characterizations of subclasses and variations of perfect graphs: A survey

A graph is perfect if the chromatic number is equal to the clique number for every induced subgraph of the graph. Perfect graphs were defined by Berge in the sixties. In this survey we present known results about partial characterizations by forbidden induced subgraphs of different graph classes related to perfect graphs. We analyze a variation of perfect graphs, clique-perfect graphs, and two subclasses of perfect graphs, coordinated graphs and balanced graphs.     

图类αK_a∪βCP(b)中的一类特殊整谱图

图G是一个简单图,图G的补图记为G,如果G的谱完全由整数组成,就称G是整谱图.鸡尾酒会图CP(n)=K_(2n)-nK2(K_(2n是完全图)和完全图K_a都是整谱图.μ_1表示图类αK_a∪βCP(b)的一个主特征值,确定了当μ_1=2a并且a-1>2b-2时,图类αK_a∪βCP(b)中的所有的整谱图.     

Polar cographs

Polar graphs are a natural extension of some classes of graphs like bipartite graphs, split graphs and complements of bipartite graphs. A graph is (s,k)-polar if there exists a partition A,B of its vertex set such that A induces a complete s-partite graph (i.e., a collection of at most s disjoint stable sets with complete links between all sets) and B a disjoint union of at most k cliques (i.e., the complement of a complete k-partite graph).Recognizing a polar graph is known to be NP-complete. These graphs have not been extensively studied and no good characterization is known. Here we consider the class of polar graphs which are also cographs (graphs without induced path on four vertices). We provide a characterization in terms of forbidden subgraphs. Besides, we give an algorithm in time O(n) for finding a largest induced polar subgraph in cographs; this also serves as a polar cograph recognition algorithm. We examine also the monopolar cographs which are the (s,k)-polar cographs where min(s,k)?1. A characterization of these graphs by forbidden subgraphs is given. Some open questions related to polarity are discussed.     

完全图删边子图的子刻画

In this paper, we show that some edges-deleted subgraphs of complete graph are determined by their spectrum with respect to the adjacency matrix as well as the Laplacian matrix.     

Marginal AMP chain graphs

We present a new family of models that is based on graphs that may have undirected, directed and bidirected edges. We name these new models marginal AMP (MAMP) chain graphs because each of them is Markov equivalent to some AMP chain graph under marginalization of some of its nodes. However, MAMP chain graphs do not only subsume AMP chain graphs but also multivariate regression chain graphs. We describe global and pairwise Markov properties for MAMP chain graphs and prove their equivalence for compositional graphoids. We also characterize when two MAMP chain graphs are Markov equivalent.For Gaussian probability distributions, we also show that every MAMP chain graph is Markov equivalent to some directed and acyclic graph with deterministic nodes under marginalization and conditioning on some of its nodes. This is important because it implies that the independence model represented by a MAMP chain graph can be accounted for by some data generating process that is partially observed and has selection bias. Finally, we modify MAMP chain graphs so that they are closed under marginalization for Gaussian probability distributions. This is a desirable feature because it guarantees parsimonious models under marginalization.     

Homomorphism–homogeneous graphs

We answer two open questions posed by Cameron and Nesetril concerning homomorphism–homogeneous graphs. In particular we show, by giving a characterization of these graphs, that extendability to monomorphism or to homomorphism leads to the same class of graphs when defining homomorphism–homogeneity. Further, we show that there are homomorphism–homogeneous graphs that do not contain the Rado graph as a spanning subgraph answering the second open question. We also treat the case of homomorphism–homogeneous graphs with loops allowed, showing that the corresponding decision problem is co–NP complete. Finally, we extend the list of considered morphism–types and show that the graphs for which monomorphisms can be extended to epimor‐phisms are complements of homomorphism–homogeneous graphs. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 253–261, 2010     

Characterizing distance-regularity of graphs by the spectrum

We characterize the distance-regular Ivanov-Ivanov-Faradjev graph from the spectrum, and construct cospectral graphs of the Johnson graphs, Doubled Odd graphs, Grassmann graphs, Doubled Grassmann graphs, antipodal covers of complete bipartite graphs, and many of the Taylor graphs. We survey the known results on cospectral graphs of the Hamming graphs, and of all distance-regular graphs on at most 70 vertices.     

On the nullity of bipartite graphs

The nullity of a graph is defined to be the multiplicity of the eigenvalue zero in the spectrum of the adjacency matrix of the graph. In this paper, we obtain the nullity set of bipartite graphs of order n, and characterize the bipartite graphs with nullity n-4 and the regular bipartite graphs with nullity n-6.     

On a signless Laplacian spectral characterization of -shape trees

Let M be an associated matrix of a graph G (the adjacency, Laplacian and signless Laplacian matrix). Two graphs are said to be cospectral with respect to M if they have the same M spectrum. A graph is said to be determined by M spectrum if there is no other non-isomorphic graph with the same spectrum with respect to M. It is shown that T-shape trees are determined by their Laplacian spectra. Moreover among them those are determined by their adjacency spectra are characterized. In this paper, we identify graphs which are cospectral to a given T-shape tree with respect to the signless Laplacian matrix. Subsequently, T-shape trees which are determined by their signless Laplacian spectra are identified.     

On Balanced Graphs

Berge defined a hypergraph to be balanced if its incidence matrix is balanced. We consider this concept applied to graphs, and call a graph to be balanced when its clique matrix is balanced. Characterizations of balanced graphs by forbidden subgraphs and by clique subgraphs are proved in this work. Using properties of domination we define four subclasses of balanced graphs. Two of them are characterized by 0–1 matrices and can be recognized in polynomial time. Furthermore, we propose polynomial time combinatorial algorithms for the problems of stable set, clique-independent set and clique-transversal for one of these subclasses of balanced graphs. Finally, we analyse the behavior of balanced graphs and these four subclasses under the clique graph operator. Received: April, 2004     

On the asymptotic behavior of graphs determined by their generalized spectra

In Wang and Xu (2006) [15] and [16] the authors introduced a family of graphs H_n and gave some methods for finding graphs among this family that are determined by their generalized spectra. This paper is a continuation of our previous work. We further show that almost all graphs in H_n are determined by their generalized spectra. This gives some evidences for the conjecture that almost all graphs are determined by their generalized spectra.