强正则自补图的一个注记

Kotzig put forward a question on strongly-regular self-complementary graphs, that is, for any natural number k, whether there exists a strongly-regular self- complementary graph whose order is 4k 1, where 4k 1=x2 y2, x and y are positive integers; what is the minimum number that made there exist at least two non-isomorphic strongly-regular self-complementary graphs. In this paper, we use two famous lemmas to generalize the existential conditions for strongly-regular self-complementary circular graphs with 4k 1 orders.     

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.     

Some Identities for Enumerators of Circulant Graphs

We establish analytically several new identities connecting enumerators of different types of circulant graphs mainly of prime, twice prime and prime-squared orders. In particular, it is shown that the half-sum of the number of undirected circulants and the number of undirected self-complementary circulants of prime order is equal to the number of directed self-complementary circulants of the same order. Several identities hold only for prime orders p such that (p + 1)/2 is also prime. Some conjectured generalizations and interpretations are discussed.     

Self-complementary Cayley Graphs of Extraspecial p-groups

This paper constructs several families of self-complementary Cayley graphs of extraspecial p-groups, where p is a prime and congruent to 1 modulo 4.     

On finite self-complementary metacirculants

We prove that the automorphism group of a self-complementary metacirculant is either soluble or has \(\mathrm{A}_5\) as the only insoluble composition factor, extending a result of Li and Praeger which says the automorphism group of a self-complementary circulant is soluble. The proof involves a construction of self-complementary metacirculants which are Cayley graphs and have insoluble automorphism groups. To the best of our knowledge, these are the first examples of self-complementary graphs with this property.     

On Sylow Subgraphs of Vertex-Transitive Self-Complementary Graphs

One of the basic facts of group theory is that each finite groupcontains a Sylow p-subgroup for each prime p which divides theorder of the group. In this note we show that each vertex-transitiveself- complementary graph has an analogous property. As a consequenceof this fact, we obtain that each prime divisor p of the orderof a vertex-transitive self-complementary graph satisfies thecongruence p^m 1(mod 4), where p^m is the highest power of pwhich divides the order of the graph. 1991 Mathematics SubjectClassification 05C25, 20B25.     

Cerf Theory for Graphs

We develop a deformation theory for k-parameter families ofpointed marked graphs with fixed fundamental group F_n. Applicationsinclude a simple geometric proof of stability of the rationalhomology of Aut(F_n), computations of the rational homology insmall dimensions, proofs that various natural complexes of freefactorizations of F_n are highly connected, and an improvementon the stability range for the integral homology of Aut(F_n).     

Total Colourings of Graphs

We prove that the TCC (Total Colouring Conjecture) is true forcomplete r-partite graphs, which extends a result of M. Rosenfeld.We also give an alternative, slightly simpler proof of an earlierresult (which says that the TCC is true for graphs having maximumdegree 3) obtained independently by M. Rosenfeld and N. Vijayaditya.     

{Omega}-Covers of Graphs

Given a group G, a G-set and a graph we present a constructionfor a family of graphs, the -covers of . A particular exampleof this construction gives a girth 17 cubic graph with 2530vertices. 2000 Mathematics Subject Classification 05C25, 05C35.     

Self-complementary graphs

In this paper a new algorithm is given for the construction of self-complementary graphs, and results concerning structural properties and adjacency matrices of these graphs are presented.     

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.     

Purely Infinite Cuntz-Krieger Algebras of Directed Graphs

For arbitrary infinite directed graphs E, the characterisationof the (not necessarily simple) Cuntz–Krieger algebrasC*(E) which are purely infinite in the sense of Kirchberg–Rørdamis given. It is also shown that C*(E) has real rank zero ifand only if the graph E satisfies Condition (K). 2000 MathematicsSubject Classification 46L05.     

On almost self-complementary graphs

A graph is called almost self-complementary if it is isomorphic to one of its almost complements X^c-I, where X^c denotes the complement of X and I a perfect matching (1-factor) in X^c. Almost self-complementary circulant graphs were first studied by Dobson and Šajna [Almost self-complementary circulant graphs, Discrete Math. 278 (2004) 23-44]. In this paper we investigate some of the properties and constructions of general almost self-complementary graphs. In particular, we give necessary and sufficient conditions on the order of an almost self-complementary regular graph, and construct infinite families of almost self-complementary regular graphs, almost self-complementary vertex-transitive graphs, and non-cyclically almost self-complementary circulant graphs.     

A class of self-complementary graphs and lower bounds of some ramsey numbers

A method is described of constructing a class of self-complementary graphs, that includes a self-complementary graph, containing no K₅, with 41 vertices and a self-complementary graph, containing no K₇, with 113 vertices. The latter construction gives the improved Ramsey number lower bound r(7, 7) ≥ 114.     

Symmetric Graphs and Flag Graphs

 With any G-symmetric graph Γ admitting a nontrivial G-invariant partition , we may associate a natural “cross-sectional” geometry, namely the 1-design in which for and if and only if α is adjacent to at least one vertex in C, where and is the neighbourhood of B in the quotient graph of Γ with respect to . In a vast number of cases, the dual 1-design of contains no repeated blocks, that is, distinct vertices of B are incident in with distinct subsets of blocks of . The purpose of this paper is to give a general construction of such graphs, and then prove that it produces all of them. In particular, we show that such graphs can be reconstructed from and the induced action of G on . The construction reveals a close connection between such graphs and certain G-point-transitive and G-block-transitive 1-designs. By using this construction we give a characterization of G-symmetric graphs such that there is at most one edge between any two blocks of . This leads to, in a subsequent paper, a construction of G-symmetric graphs such that and each is incident in with vertices of B. The work was supported by a discovery-project grant from the Australian Research Council. Received April 24, 2001; in revised form October 9, 2002 Published online May 9, 2003     

Characterizing Flag Graphs and Induced Subgraphs of Cartesian Product Graphs

The vertices of the flag graph Φ(P) of a graded poset P are its maximal chains. Two vertices are adjacent whenever two maximal chains differ in exactly one element. In this paper we characterize induced subgraphs of Cartesian product graphs and flag graphs of graded posets. The latter class of graphs lies between isometric and induced subgraphs of Cartesian products in the embedding structure theory. Both characterization use certain edge-labelings of graphs.     

Bubble-sort图和Modified Bubble-sort图的自同构群

Bubble-Sort图和Modified Bubble-Sort图是两类特殊的Cayley图,由于其在网络构建中的应用而受到广泛关注.本文完全确定了这两类图的自同构群.     

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.     

Heat Kernel Estimates on Weighted Graphs

We prove upper and lower heat kernel bounds for the Laplacianon weighted graphs which include the case that the weights haveno strictly positive lower bound. Our estimates give rise toa very explicit probabilistic interpretation, and can be formulatedin terms of a weighted metric. Interestingly, this metric isnot equivalent to the intrinsic metric. 1991 Mathematics SubjectClassification 39A12.     

Common Multiples of Complete Graphs

A graph H is said to divide a graph G if there exists a setS of subgraphs of G, all isomorphic to H, such that the edgeset of G is partitioned by the edge sets of the subgraphs inS. Thus, a graph G is a common multiple of two graphs if eachof the two graphs divides G. This paper considers common multiples of a complete graph oforder m and a complete graph of order n. The complete graphof order n is denoted K_n. In particular, for all positive integersn, the set of integers q for which there exists a common multipleof K₃ and K_n having precisely q edges is determined. It is shown that there exists a common multiple of K₃ and K_nhaving q edges if and only if q 0 (mod 3), q 0 (mod n2) and (1) q 3 n2 when n 5 (mod 6); (2) q (n + 1) n2 when n is even; (3) q {36, 42, 48} when n = 4. The proof of this result uses a variety of techniques includingthe use of Johnson graphs, Skolem and Langford sequences, andequitable partial Steiner triple systems. 2000 MathematicalSubject Classification: 05C70, 05B30, 05B07.