Maximum Order of Triangle‐Free Graphs with a Given Rank

The rank of a graph is defined to be the rank of its adjacency matrix. A graph is called reduced if it has no isolated vertices and no two vertices with the same set of neighbors. We determine the maximum order of reduced triangle‐free graphs with a given rank and characterize all such graphs achieving the maximum order.     

单圈图的最低及最高电阻地位

一个连通图的一个顶点的电阻地位是这个顶点到该图的其它所有顶点的电阻距离之和. 一个连通图的最低(最高)电阻地位是这个图的所有顶点的电阻地位的最小值(最大值). 我们确定了在给定阶数的单圈图中最低(最高)电阻地位的极值和相应的极图,还讨论了单圈图的最低(最高)电阻地位与围长的关系.     

Rank numbers for some trees and unicyclic graphs

A ranking on a graph is an assignment of positive integers to its vertices such that any path between two vertices of the same rank contains a vertex of strictly larger rank. The rank number of a graph is the fewest number of labels that can be used in a ranking. In this paper we determine rank numbers for some trees and unicyclic graphs.     

Zero forcing parameters and minimum rank problems

The zero forcing number Z(G), which is the minimum number of vertices in a zero forcing set of a graph G, is used to study the maximum nullity/minimum rank of the family of symmetric matrices described by G. It is shown that for a connected graph of order at least two, no vertex is in every zero forcing set. The positive semidefinite zero forcing number Z₊(G) is introduced, and shown to be equal to |G|-OS(G), where OS(G) is the recently defined ordered set number that is a lower bound for minimum positive semidefinite rank. The positive semidefinite zero forcing number is applied to the computation of positive semidefinite minimum rank of certain graphs. An example of a graph for which the real positive symmetric semidefinite minimum rank is greater than the complex Hermitian positive semidefinite minimum rank is presented.     

Maximal planar graphs of diameter two

A maximal planar graph is a simple planar graph in which every face is a triangle. We show here that such graphs with maximum degree Δ and diameter two have no more than 3/2Δ + 1 vertices. We also show that there exist maximal planar graphs with diameter two and exactly [3/2Δ + 1] vertices.     

On the Maximum Number of Cliques in a Graph

A clique is a set of pairwise adjacent vertices in a graph. We determine the maximum number of cliques in a graph for the following graph classes: (1) graphs with n vertices and m edges; (2) graphs with n vertices, m edges, and maximum degree Δ; (3) d-degenerate graphs with n vertices and m edges; (4) planar graphs with n vertices and m edges; and (5) graphs with n vertices and no K₅-minor or no K_3,3-minor. For example, the maximum number of cliques in a planar graph with n vertices is 8(n − 2). Research supported by a Marie Curie Fellowship of the European Community under contract 023865, and by the projects MCYT-FEDER BFM2003-00368 and Gen. Cat 2001SGR00224.     

A fast algorithm for the maximum clique problem

Given a graph, in the maximum clique problem, one desires to find the largest number of vertices, any two of which are adjacent. A branch-and-bound algorithm for the maximum clique problem—which is computationally equivalent to the maximum independent (stable) set problem—is presented with the vertex order taken from a coloring of the vertices and with a new pruning strategy. The algorithm performs successfully for many instances when applied to random graphs and DIMACS benchmark graphs.     

The bondage number of graphs on topological surfaces and Teschner’s conjecture

The bondage number of a graph is the smallest number of its edges whose removal results in a graph having a larger domination number. We provide constant upper bounds for the bondage number of graphs on topological surfaces, and improve upper bounds for the bondage number in terms of the maximum vertex degree and the orientable and non-orientable genera of graphs. Also, we present stronger upper bounds for graphs with no triangles and graphs with the number of vertices larger than a certain threshold in terms of graph genera. This settles Teschner’s Conjecture in affirmative for almost all graphs. As an auxiliary result, we show tight lower bounds for the number of vertices of graphs 2-cell embeddable on topological surfaces of a given genus.     

Weakly triangulated graphs

A graph is triangulated if it has no chordless cycle with four or more vertices. It follows that the complement of a triangulated graph cannot contain a chordless cycle with five or more vertices. We introduce a class of graphs (namely, weakly triangulated graphs) which includes both triangulated graphs and complements of triangulated graphs (we define a graph as weakly triangulated if neither it nor its complement contains a chordless cycle with five or more vertices). Our main result is a structural theorem which leads to a proof that weakly triangulated graphs are perfect.     

Non rank 3 strongly regular graphs with the 5-vertex condition

Three new strongly regular graphs on 256, 120, and 135 vertices are described in this paper. They satisfy thet-vertex condition — in the sense of [1] — on the edges and on the nonedges fort=4 but they are not rank 3 graphs. The problem to search for any such graph was discussed on a folklore level several times and was fixed in [2]. Here the graph on 256 vertices satisfies even the 5-vertex condition, and has the graphs on 120 and 135 vertices as its subgraphs. The existence of these graphs was announced in [3] and [4]. [4] contains M. H. Klin's interpretation of the graph on 120 vertices. Further results concerning these graphs were obtained by A. E. Brouwer, cf. [5].     

The minimum semidefinite rank of a triangle-free graph

We employ a result of Moshe Rosenfeld to show that the minimum semidefinite rank of a triangle-free graph with no isolated vertex must be at least half the number of its vertices. We define a Rosenfeld graph to be such a graph that achieves equality in this bound, and we explore the structure of these special graphs. Their structure turns out to be intimately connected with the zero-nonzero patterns of the unitary matrices. Finally, we suggest an exploration of the connection between the girth of a graph and its minimum semidefinite rank, and provide a conjecture in this direction.     

定向图的斜秩

定向图Gσ是一个不含有环(loop)和重边的有向图,其中G称作它的基图.S(Gσ)是Gσ的斜邻接矩阵.S(Gσ)的秩称为Gσ的斜秩,记为sr(Gσ).定向图的斜邻接矩阵是斜对称的,因而,它的斜秩是偶数.本文主要考虑简单定向图的斜秩,首先给出斜秩的一些简单基本知识,紧接着分别刻画斜秩是2的定向图和斜秩是4的带有悬挂点的定向图;其次利用匹配数给出具有n个顶点、围长是k的单圈图的斜秩表达式;作为推论,列出斜秩是4的所有单圈图和带有悬挂点的双圈图;另外研究具有n个顶点、围长是k的单圈图的图类中斜秩的最小值,并刻画了极图;最后研究斜邻接矩阵是非奇异的定向单圈图.     

Rank three permutation groups with rank three subconstituents

Finite permutation groups of rank 3 such that both the subconstituents have rank 3 are classified. This is equivalent to classifying all finite undirected graphs with the following property: every isomorphism between subgraphs on at most three vertices is a restriction of an automorphism of the graph.     

Connected graphs without long paths

We determine the maximum number of edges in a connected graph with n vertices if it contains no path with k+1 vertices. We also determine the extremal graphs.     

Linearly independent vertices and minimum semidefinite rank

We study the minimum semidefinite rank of a graph using vector representations of the graph and of certain subgraphs. We present a sufficient condition for when the vectors corresponding to a set of vertices of a graph must be linearly independent in any vector representation of that graph, and conjecture that the resulting graph invariant is equal to minimum semidefinite rank. Rotation of vector representations by a unitary matrix allows us to find the minimum semidefinite rank of the join of two graphs. We also improve upon previous results concerning the effect on minimum semidefinite rank of the removal of a vertex.     

Hereditary dominating pair graphs

An asteroidal triple (AT) is a set of vertices such that each pair of vertices is joined by a path that avoids the neighborhood of the third. Every AT-free graph contains a dominating pair, a pair of vertices such that for every path between them, every vertex of the graph is within distance one of the path. We say that a graph is a hereditary dominating pair (HDP) graph if each of its connected induced subgraphs contains a dominating pair. In this paper we introduce the notion of frame HDP graphs in order to capture the structure of HDP graphs that contain asteroidal triples. We also determine the maximum diameter of frame HDP graphs.     

具有最小度距离的双圈图

记G（n）为所有n阶连通简单双圈图所构成的集合．本文主要讨论G（n）按其度距离从小到大进行排序的问题，并确定了该序的前两个图及其相应的度距离，其中具有最小度距离的图是由星图K1,n-1的一个悬挂点与另外两个悬挂点之间各连上一条边所得的图Sn．     

Almost self-centered graphs

The center of a graph is the set of vertices with minimum eccentricity. Graphs in which all vertices are central are called self-centered graphs. In this paper almost self-centered (ASC) graphs are introduced as the graphs with exactly two non-central vertices. The block structure of these graphs is described and constructions for generating such graphs are proposed. Embeddings of arbitrary graphs into ASC graphs are studied. In particular it is shown that any graph can be embedded into an ASC graph of prescribed radius. Embeddings into ASC graphs of radius two are studied in more detail. ASC index of a graph G is introduced as the smallest number of vertices needed to add to G such that G is an induced subgraph of an ASC graph.     

若干图类的Wiener指数的极值

一个图的Wiener指数是指这个图中所有点对的距离和.Wiener指数在理论化学中有广泛应用. 本文刻画了给定顶点数及特定参数如色数或团数的图中Wiener指数达最小值的图, 同时也刻画了给定顶点数及团数的图中Wiener指数达最大值的图.     

On the Number of Vertices with Specified Eccentricity

The eccentricity of a vertex v in a graph is the maximum of the distances from v to all other vertices. The diameter of a graph is the maximum of the eccentricities of its vertices. Fix the parameters n, d, c. Over all graphs with order n and diameter d, we determine the maximum (within 1) and the minimum of the number of vertices with eccentricity c. Revised: May 7, 1999