正则图的变换图的谱

设G是一个图,类似全图的定义,可以定义G的8种变换图.如果G是正则图,那么图G的变换图的谱都可以由图G的谱计算得到.     

On the number of matchings of graphs formed by a graph operation

Let G be a simple graph. Define R(G) to be the graph obtained from G by adding a new vertex e* corresponding to each edge e = (a,b) of G and by joining each new vertex e* to the end vertices a and b of the edge e corresponding to it. In this paper, we prove that the number of matchings of R(G) is completely determined by the degree sequence of vertices of G.     

Deza graphs: A generalization of strongly regular graph

We consider the following generalization of strongly regular graphs. A graph G is a Deza graph if it is regular and the number of common neighbors of two distinct vertices takes on one of two values (not necessarily depending on the adjacency of the two vertices). We introduce several ways to construct Deza graphs, and develop some basic theory. We also list all diameter two Deza graphs which are not strongly regular and have at most 13 vertices.     

Covering a graph by complete bipartite graphs

We prove the following theorem: the edge set of every graph G on n vertices can be partitioned into the disjoint union of complete bipartite graphs such that each vertex is contained by at most c(n/log n) of the bipartite graphs.     

A generalization of de Bruijn graphs and classification of endomorphisms of Cuntz algebras by graph invariants

The classification problem of endomorphisms of the Cuntz algebra O_N\mathcal{O}_{N} is solved by using graph theory. We introduce permutative de Bruijn graphs as generalizations of de Bruijn graphs. Branching laws for a permutative endomorphism ρ of O_N\mathcal{O}_{N} are computed by using the permutative de Bruijn graph associated with ρ. According to this correspondence between endomorphisms and graphs, we classify permutative endomorphisms of O_N\mathcal{O}_{N} by graph invariants concretely.     

On a generalization of linecritical graphs

Let β(G) be the maximal β such that for any edge xy of G there is an independent β-set that contains no neighbours of x and y. Then $\text{0}\text{}\text{?}\text{β(G)}\text{}\text{?}\text{α(G)?1}$ and G is linecritical iff β(G) = α(G)?1. We determine the minimal connected graphs for any given β(G) or for any given β(G) and α(G). We study the case when β(G)??2 and give upper bounds for the minimal valencies. We generalize some results on linecritical graphs of [1] and [4].     

Computing the boxicity of a graph by covering its complement by cointerval graphs

If $\text{F}$ is a family of sets, its intersection graph has the sets in $\text{F}$ as vertices and an edge between two sets if and only if they overlap. This paper investigates the concept of boxicity of a graph G, the smallest n such that G is the intersection graph of boxes in Euclidean n-space. The boxicity, b(G), was introduced by Roberts in 1969 and has since been studied by Cohen, Gabai, and Trotter. The concept has applications to niche overlap (competition) in ecology and to problems of fleet maintenance in operations research. These applications will be described briefly. While the problem of computing boxicity is in general a difficult problem (it is NP-complete), this paper develops techniques for computing boxicity which give useful bounds. They are based on the simple observation that b(G)≤k if and only if there is an edge covering of $\text{G}$ by spanning subgraphs of $\text{G}$, each of which is a cointerval graph, the complement of an interval graph (a graph of boxicity ≤1.).     

A class of antimagic join graphs

A labeling f of a graph G is a bijection from its edge set E(G) to the set {1, 2, . . . , |E(G)|}, which is antimagic if for any distinct vertices x and y, the sum of the labels on edges incident to x is different from the sum of the labels on edges incident to y. A graph G is antimagic if G has an f which is antimagic. Hartsfield and Ringel conjectured in 1990 that every connected graph other than K 2 is antimagic. In this paper, we show that if G 1 is an n-vertex graph with minimum degree at least r, and G 2 is an m-vertex graph with maximum degree at most 2r-1 (m ≥ n), then G1 ∨ G2 is antimagic.     

联图的圈基

MacLane于1937年给出了圈基方面的重要定理: 图G是平面图, 当且仅当图G有2-重基. 连通图G_1和G_2的联图G_1\vee G_2指的是在它们的不交并G_1\bigcup G_2上添加边集(u,v)|u\in V(G_1), v\in V(G_2). 对G_1和G_2的联图G_1\vee G_2的圈基重数进行了研究, 得到了一个上界, 改进了Zare的结果. 并在此基础之上, 进一步得到特殊联图C_m\vee C_n的圈基重数的一个上界.     

On a class of polynomials obtained from the circuits in a graph and its application to characteristics polynomials of graphs

Let G be a graph. With each circuit α in G, we can associate a weight w_α, A circuit cover of G is a spanning subgraph of G in which every component is a circuit. With every circuit cover of G, we can associate the monomial Π_αw_α, where the product is taken over all components of the cover. The circuit polynomial of G is ΣΠ_αw_α, where the summation is taken over all circuit covers in G. We show that the characteristics polynomial of G is a special case of its circuit polynomial. Previously obtained and also new results for characteristic polynomials are easily deduced. We also derive the circuit polynomials of various classes of graphs.     

Ear decompositions of join covered graphs

Join covered graphs are ±1-weighted graphs, without negative circuits, in which every edge lies in a zero-weight circuit. Join covered graphs are a natural generalization of matching covered graphs. Many important properties of matching covered graphs have been generalized to join covered graphs. In this paper, we generalize Lovász and Plummerʼs ear decomposition theorem of matching covered graphs to join covered graphs.     

The inertia set of the join of graphs

Let G=(V,E) be a graph with V={1,2,…,n}. Denote by S(G) the set of all real symmetric n×n matrices A=[a_i,j] with a_i,j≠0, i≠j if and only if ij is an edge of G. Denote by I^↗(G) the set of all pairs (p,q) of natural numbers such that there exists a matrix A∈S(G) with at most p positive and q negative eigenvalues. We show that if G is the join of G₁ and G₂, then I^↗(G)?{(1,1)}=I^↗(G₁∨K₁)∩I^↗(G₂∨K₁)?{(1,1)}. Further, we show that if G is a graph with s isolated vertices, then , where denotes the graph obtained from G be removing all isolated vertices, and we give a combinatorial characterization of graphs G with (1,1)∈I^↗(G). We use these results to determine I^↗(G) for every complete multipartite graph G.     

On the join of graphs and chromatic uniqueness

A graph is chromatically unique if it is uniquely determined by its chromatic polynomial. Let G be a chromatically unique graph and let K_m denote the complete graph on m vertices. This paper is mainly concerned with the chromaticity of K_m + G where + denotes the join of graphs. Also, it is shown that a large family of connected vertextransitive graphs that are not chromatically unique can be obtained by taking the join of some vertex-transitive graphs. © 1995 John Wiley & Sons, Inc.     

A generalization of outerplanar graphs

Let G be a planar graph and W a set of vertices, G is W-outerplanar if it can be embedded in the plane so that all vertices of W lie on the exterior face. We give a characterization of these graphs by forbidden subgraphs, an upper bound on the number of edges, and other properties which lead to an algorithm of W-outerplanarity testing.     

A generalization of total graphs

Let R be a commutative ring with nonzero identity, \(L_{n}(R)\) be the set of all lower triangular \(n\times n\) matrices, and U be a triangular subset of \(R^{n}\), i.e., the product of any lower triangular matrix with the transpose of any element of U belongs to U. The graph \(GT^{n}_{U}(R^n)\) is a simple graph whose vertices consists of all elements of \(R^{n}\), and two distinct vertices \((x_{1},\dots ,x_{n})\) and \((y_{1},\dots ,y_{n})\) are adjacent if and only if \((x_{1}+y_{1}, \ldots ,x_{n}+y_{n})\in U\). The graph \(GT^{n}_{U}(R^n)\) is a generalization for total graphs. In this paper, we investigate the basic properties of \(GT^{n}_{U}(R^n)\). Moreover, we study the planarity of the graphs \(GT^{n}_{U}(U)\), \(GT^{n}_{U}(R^{n}{\setminus } U)\) and \(GT^{n}_{U}(R^n)\).