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.     

Explicit Construction and Uniqueness for Universal Operator Algebras of Directed Graphs

Given a directed graph, there exist a universal operator algebraand universal C*-algebra associated to the directed graph. Inthis paper we give intrinsic constructions for these objects.We also provide an explicit construction for the maximal C*-algebraof an operator algebra. We discuss uniqueness of the universalalgebras for finite graphs, showing that for finite graphs thegraph is an isomorphism invariant for the universal operatoralgebra of a directed graph. We show that the underlying undirectedgraph is a Banach algebra isomorphism invariant for the universalC*-algebra of a directed graph.     

Entanglement in Percolation

We study finite and infinite entangled graphs in the bond percolationprocess in three dimensions with density p. After a discussionof the relevant definitions, the entanglement critical probabilitiesare defined. The size of the maximal entangled graph at theorigin is studied for small p, and it is shown that this graphhas radius whose tail decays at least as fast as exp(–n/logn); indeed, the logarithm may be replaced by any iterate oflogarithm for an appropriate positive constant . We explorethe question of almost sure uniqueness of the infinite maximalopen entangled graph when p is large, and we establish two relevanttheorems. We make several conjectures concerning the propertiesof entangled graphs in percolation. http://www.statslab.cam.ac.uk/\simgrg/1991 Mathematics Subject Classification: primary 60K35; secondary05C10, 57M25, 82B41, 82B43, 82D60.     

广义图K(n,m)的全色数

1965年,M.Behzad和Vizing分别提出了著名的全着色猜想:即对于简单图G有:XT(G)≤△+2,其中△是图G的最大度.本文确定了完全图Kn的广义图K(n,m)的全色数,并利用它证明了Lm×Kn(m≥3)是第Ⅰ型的.     

A Polynomial Invariant of Graphs On Orientable Surfaces

We consider cyclic graphs, that is, graphs with cyclic ordersat the vertices, corresponding to 2-cell embeddings of graphsinto orientable surfaces, or combinatorial maps. We constructa three variable polynomial invariant of these objects, thecyclic graph polynomial, which has many of the useful propertiesof the Tutte polynomial. Although the cyclic graph polynomialgeneralizes the Tutte polynomial, its definition is very different,and it depends on the embedding in an essential way. 2000 MathematicalSubject Classification: 05C10.     

On superperfect noncomparability graphs

The class of superperfect graphs, which was previously studied by A. J. Hoffman, E. L. Johnson, and M. C. Golumbic, is a proper subclass of the class of perfect graphs; further, it properly contains the class of comparability graphs. In his book, Golumbic proves that, for split graphs, G is a comparability graph if and only if G is superperfect. Moreover, the fact that split graphs are exactly those graphs which are both triangulated and cotriangulated motivated Golumbic to ask if it is true or false that, for triangulated (or cotriangulated) graphs, G is a comparability graph if and only if G is superperfect. In the present paper, we determine those members of Gallai's list of minimal noncomparability graphs which are superperfect and, as a consequence, we find that the answer to the above question is “false” for triangulated and “true” for cotriangulated graphs.     

Splitting of Finite Covers of N0-Categorical Structures

Suppose that W is a countable ₀-categorical structure. We investigatethe question as to whether every finite cover of W splits, thatis, has an expansion which is a trivial finite cover of W. Weshow that for most primitive structures W which are homogeneousfor a single binary relation (homogeneous graphs, partial orderings,the Henson digraphs, ...) any finite cover splits. However,in contrast to this, we show that there are non-split covers(with finite kernels) of the countable, universal, homogeneouslocal order.     

Shift graphs on precompact families of finite sets of natural numbers

We study graphs defined on families of finite sets of natural numbers and their chromatic properties. Of particular interest are graphs for which the edge relation is given by the shift. We show that when considering shift graphs with infinite chromatic number, one can center attention on graphs defined on precompact thin families. We define a quasi-order relation on the collection of uniform families defined in terms of homomorphisms between their corresponding shift graphs, and show that there are descending ${\omega }_1$-sequences. Specker graphs are also considered and their relation with shift graphs is established. We characterize the family of Specker graphs which contain a homomorphic image of a shift graph.     

Convex Bodies, Graphs and Partial Orders

A convex corner is a compact convex down-set of full dimensionin Rⁿ. Convex corners arise in graph theory, for instance asstable set polytopes of graphs. They are also natural objects of study in geometry, as they correspond to 1-unconditionalnorms in an obvious way. In this paper, we study a parameterof convex corners, which we call the content, that is relatedto the volume. This parameter has appeared implicitly before:both in geometry, chiefly in a paper of Meyer (Israel J. Math.} 55 (1986) 317–327) effectively using content to givea proof of Saint-Raymond's Inequality on the volume product of a convex corner, and in combinatorics, especially in apaper of Sidorenko (Order} 8 (1991) 331–340) relatingcontent to the number of linear extensions of a partial order.One of our main aims is to expose connections between workin these two areas. We prove many new results, giving in particular various generalizations of Saint-Raymond's Inequality. Contentalso behaves well under the operation of pointwise product oftwo convex corners; our results enable us to give counter-examplesto two conjectures of Bollobás and Leader Oper. TheoryAdv. Appl. 77 (1995) 13–24) on pointwise products. 1991Mathematics Subject Classification: 52C07, 51M25, 52B11, 05C60,06A07.     

Degree-equipartite graphs

A graph $G$ of order $2n$ is called degree-equipartite if for every $n$-element set $A?V\left(G\right)$, the degree sequences of the induced subgraphs $G\left[A\right]$ and $G[V\left(G\right)?A]$ are the same. In this paper, we characterize all degree-equipartite graphs. This answers Problem 1 in the paper by Grünbaum et al. [B. Grünbaum, T. Kaiser, D. Král, and M. Rosenfeld, Equipartite graphs, Israel J. Math. 168 (2008) 431–444].     

The relative degree and large complete minors in infinite graphs

Finite graphs of large minimum degree have large complete (topological) minors. We propose a new and very natural notion, the relative degree of an end, which makes it possible to extend this fact to locally finite graphs and to graphs with countably many ends. We conjecture the extension to be true for all infinite graphs.     

Total chromatic number of complete r-partite graphs

Rosenfeld (1971) proved that the Total Colouring Conjecture holds for balanced complete r-partite graphs. Bermond (1974) determined the exact total chromatic number of every balanced complete r-partite graph. Rosenfeld's result had been generalized recently to complete r-partite graphs by Yap (1989). The main result of this paper is to prove that the total chromatic number of every complete r-partite graph G of odd order is Δ (G) + 1. This result gives a partial generalization of Bermond's theorem.     

(2)-pancyclic graphs

We introduce the class of (2)-pancyclic graphs, which are simple undirected finite connected graphs of order $n$ having exactly two cycles of length $p$ for each $p$ satisfying $3\le p\le n$, analyze their properties, and give several examples of such graphs, among which are the smallest.     

Minimal separators in P4-tidy graphs

We show that $P_4$-tidy graphs have a linear number of minimal separators and present an algorithm to list them in linear time, extending an algorithm for $P_4$-sparse graphs given by Nikolopoulos and Palios. We also give bounds on the number and total size of all minimal separators of $P_4$-tidy and $P_4$-lite graphs. Moreover, we show that these bounds are tight for such classes of graphs.     

The Intersection of Two Infinite Matroids

Conjecture: Let M and N be two matroids (possibly of infiniteranks) on the same set S. Then there exists a set I independentin both M and N, which can be partitioned as I=HK, where sp_M(H)sp_N(K)=S.This conjecture is an extension of Edmonds' matroid intersectiontheorem to the infinite case. We prove the conjecture when oneof the matroids (say M) is the sum of countably many matroidsof finite rank (the other matroid being general). For the proofwe have also to answer the following question: when does thereexist a subset of S which is spanning for M and independentin N?     

Maximality of the signless Laplacian energy

We study the problem of determining the graph with $n$ vertices having largest signless Laplacian energy. We conjecture it is the complete split graph whose independent set has (roughly) $2n∕3$ vertices. We show that the conjecture is true for several classes of graphs. In particular, the conjecture holds for the set of all complete split graphs of order $n$, for trees, for unicyclic and bicyclic graphs. We also give conditions on the number of edges, number of cycles and number of small eigenvalues so the graph satisfies the conjecture.