Zero-Divisor Semigroups and Some Simple Graphs

In this article, we study commutative zero-divisor semigroups determined by graphs. We prove that for all n ≥ 4, the complete graph K _n together with two end vertices has a unique corresponding zero-divisor semigroup, while the complete graph K _n together with three end vertices has no corresponding semigroups. We determine all the twenty zero-divisor semigroups whose zero-divisor graphs are the complete graph K ₃ together with an end vertex.     

Maximum chromatic polynomials of 2-connected graphs

In this paper we obtain chromatic polynomials P(G; λ) of 2-connected graphs of order n that are maximum for positive integer-valued arguments λ ≧ 3. The extremal graphs are cycles C_n and these graphs are unique for every λ ≧ 3 and n ≠ 5. We also determine max{P(G; λ): G is 2-connected of order n and G ≠ C_n} and all extremal graphs relative to this property, with some consequences on the maximum number of 3-colorings in the class of 2-connected graphs of order n having _X(G) = 2 and _X(G) = 3, respectively. For every n ≧ 5 and λ ≧ 4, the first three maximum chromatic polynomials of 2-connected graphs are determined.     

The projective plane crossing number of C3 × Cn

In this paper, we show that the projective plane crossing number of the graphs C₃ × C_n is n - 1 for n ≤ 5 and 2 for n = 4. As far as we can tell from the literature, this is the first infinite family of graphs whose crossing number is known on a single surface other than the plane. © 1993 John Wiley & Sons, Inc.     

Graphs with symmetric automorphism group

We investigate the properties of graphs whose automorphism group is the symmetric group. In particular, we characterize graphs on less than 2n points with group S_n, and construct all graphs on n + 3 points with group S_n. Graphs with 2n or more points and group S_n are discussed briefly.     

On graphs whose Laplacian matrices have distinct integer eigenvalues

In this paper, we investigate graphs for which the corresponding Laplacian matrix has distinct integer eigenvalues. We define the set S_i,n to be the set of all integers from 0 to n, excluding i. If there exists a graph whose Laplacian matrix has this set as its eigenvalues, we say that this set is Laplacian realizable. We investigate the sets S_i,n that are Laplacian realizable, and the structures of the graphs whose Laplacian matrix has such a set as its eigenvalues. We characterize those i < n such that S_i,n is Laplacian realizable, and show that for certain values of i, the set S_i,n is realized by a unique graph. Finally, we conjecture that S_n,n is not Laplacian realizable for n ≥ 2 and show that the conjecture holds for certain values of n. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Almost all steinhaus graphs have diameter 2

A Steinhaus graph is a graph with n vertices whose adjacency matrix (a_{i, j}) satisfies the condition that a_{i, j} ? a_{a--1, j--1} + a _{i--1, j} (mod 2) for each 1 < i < j ≤ n. It is clear that a Steinhaus graph is determined by its first row. In [3] Bringham and Dutton conjecture that almost all Steinhaus graphs have diameter 2. That is, as n approaches infinity, the ratio of the number of Steinhaus graphs with n vertices having diameter 2 to the total number of Steinhaus graphs approaches 1. Here we prove Bringham and Dutton's conjecture.     

The Crossing Number of Cartesian Products of Complete Bipartite Graphs K 2, m with Paths P n

Most results on the crossing number of a graph focus on the special graphs, such as Cartesian products of small graphs with paths P_n, cycles C_n or stars S_n. In this paper, we extend the results to Cartesian products of complete bipartite graphs K_2,m with paths P_n for arbitrary m ≥ 2 and n ≥ 1. Supported by the NSFC (No. 10771062) and the program for New Century Excellent Talents in University.     

Properties of almost all graphs and complexes

There are many results in the literature asserting that almost all or almost no graphs have some property. Our object is to develop a general logical theorem that will imply almost all of these results as corollaries. To this end, we propose the first-order theory of almost all graphs by presenting Axiom n which states that for each sequence of 2n distinct vertices in a graph (u₁, …, u_n, v₁, …, v_n), there exists another vertex w adjacent to each u₁ and not adjacent to any v_i. A simple counting argument proves that for each n, almost all graphs satisfy Axiom n. It is then shown that any sentence that can be stated in terms of these axioms is true in almost all graphs or in almost none. This has several immediate consequences, most of which have already been proved separately including: (1) For any graph H, almost all graphs have an induced subgraph isomorphic to H. (2) Almost no graphs are planar, or chordal, or line graphs. (3) Almost all grpahs are connected wiht diameter 2. It is also pointed out that these considerations extend to digraphs and to simplicial complexes.     

On Partitional and Other Related Graphs

The partitional graphs, which are a subclass of the sequential graphs, were recently introduced by Ichishima and Oshima (Math Comput Sci 3:39–45, 2010), and the cartesian product of a partitional graph and K ₂ was shown to be partitional, sequential, harmonious and felicitous. In this paper, we present some necessary conditions for a graph to be partitional. By means of these, we study the partitional properties of certain classes of graphs. In particular, we completely characterize the classes of the graphs B _m and K _m,2 × Q _n that are partitional. We also establish the relationships between partitional graphs and graphs with strong α-valuations as well as strongly felicitous graphs.     

The fractional chromatic number of mycielski's graphs

James Propp The most familiar construction of graphs whose clique number is much smaller than their chromatic number is due to Mycielski, who constructed a sequence G_n of triangle-free graphs with X(G_n) = n. In this article, we calculate the fractional chromatic number of G_n and show that this sequence of numbers satisfies the unexpected recurrence a_n+1 = a_n + (1/a_n). © 1995 John Wiley & Sons, Inc.     

Chaotic Numbers of Complete Bipartite Graphs and Tripartite Graphs

In this paper, we study the chaotic numbers of complete bipartite graphs and complete tripartite graphs. For the complete bipartite graphs, we find closed-form formulas of the chaotic numbers and characterize all chaotic mappings. For the complete tripartite graphs, we develop an algorithm running in O(n ⁴ ₃) time to find the chaotic numbers, with n ₃ the number of vertices in the largest partite set.Research supported by NSC 90-2115-M-036-003.The author thanks the authors of Ref. 6, since his work was motivated by their work. Also, the author thanks the referees for helpful comments which made the paper more readable.     

On quadrilaterals in layers of the cube and extremal problems for directed and oriented graphs

Erdős has conjectured that every subgraph of the n‐cube Q_n having more than (1/2 + o(1))e(Q_n) edges will contain a 4‐cycle. In this note we consider ‘layer’ graphs, namely, subgraphs of the cube spanned by the subsets of sizes k − 1, k and k + 1, where we are thinking of the vertices of Q_n as being the power set of {1,…, n}. Observe that every 4‐cycle in Q_n lies in some layer graph. We investigate the maximum density of 4‐cycle free subgraphs of layer graphs, principally the case k = 2. The questions that arise in this case are equivalent to natural questions in the extremal theory of directed and undirected graphs. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 66–82, 2000     

On the Crossing Numbers of Products of Stars and Graphs of Order Five

 There are several known exact results on the crossing numbers of Cartesian products of paths or cycles with “small” graphs. In this paper we extend these results to the Cartesian products of two specific 5-vertex graphs with the star K _{1, n} . In addition, we give the crossing number of the graph obtained by adding two edges to the graph K _{1,4, n} in such a way that these new edges join a vertex of degree n+1 of the graph K _{1,4, n} with two its vertices of the same degree. Received: December 8, 1997 Final version received: August 14, 1998     

The crossing number of K1,3,n and K2,3,n

In this article, we will determine the crossing number of the complete tripartite graphs K_1,3,n and K_2,3,n. Our proof depends on Kleitman's results for the complete bipartite graphs [D. J. Kleitman, The crossing number of K_5,n. J. Combinatorial Theory 9 (1970) 315-323].     

4类图完美匹配数目的递推求法

本文研究了4类特殊图完美匹配数目的显式表达式.利用划分,求和,再递推的方法分别给出了图3-n Z4,2-n(2-C6),2-n(2-K4)和3-n(C4-C6)的完美匹配数目的计算公式.     

Random I-colorable graphs

In this article we investigate properties of the class of all l-colorable graphs on n vertices, where l = l(n) may depend on n. Let G^l_n denote a uniformly chosen element of this class, i.e., a random l-colorable graph. For a random graph G^l_n we study in particular the property of being uniquely l-colorable. We show that not only does there exist a threshold function l = l(n) for this property, but this threshold corresponds to the chromatic number of a random graph. We also prove similar results for the class of all l-colorable graphs on n vertices with m = m(n) edges.     

The Number of Spanning Trees in <Emphasis Type="Italic">K</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis></Subscript>-Complements of Quasi-Threshold Graphs

In this paper we examine the classes of graphs whose K_n-complements are trees or quasi-threshold graphs and derive formulas for their number of spanning trees; for a subgraph H of K_n, the K_n-complement of H is the graph K_n–H which is obtained from K_n by removing the edges of H. Our proofs are based on the complement spanning-tree matrix theorem, which expresses the number of spanning trees of a graph as a function of the determinant of a matrix that can be easily constructed from the adjacency relation of the graph. Our results generalize previous results and extend the family of graphs of the form K_n–H admitting formulas for the number of their spanning trees.Final version received: March 18, 2004     

On the spectral characterization of some unicyclic graphs

Let H(n;q,n₁,n₂) be a graph with n vertices containing a cycle C_q and two hanging paths P_n1 and P_n2 attached at the same vertex of the cycle. In this paper, we prove that except for the A-cospectral graphs H(12;6,1,5) and H(12;8,2,2), no two non-isomorphic graphs of the form H(n;q,n₁,n₂) are A-cospectral. It is proved that all graphs H(n;q,n₁,n₂) are determined by their L-spectra. And all graphs H(n;q,n₁,n₂) are proved to be determined by their Q-spectra, except for graphs with a being a positive even number and with b≥4 being an even number. Moreover, the Q-cospectral graphs with these two exceptions are given.     

给定边连通度的图的最小距离谱半径(英文)

本文研究了边连通度为r的n阶连通图中距离谱半径最小的极图问题,利用组合的方法,确定了K(n-1,r)为唯一的极图,其中K(n-1,r)是由完全图K_(n-1)添加一个顶点v以及连接v与K_(n-1)中r个顶点的边所构成.上述结论推广了极图理论中的相关结果.     

Hereditarily extended properties, quasi-random graphs and not necessarily induced subgraphs

Recently much attention has been focused on the theory of quasi-random graph and hypergraph properties. The class of quasi-random graphs is defined by certain equivalent graph properties possessed by random graphs. We shall investigate propertiesP which do not imply quasi-randomnes for sequences (G _n ) of graphs on their own, but do imply if they hold not only for the whole graphG _n but also for every sufficiently large subgraph ofG _n . Here the properties are strongly connected to countingnot necessarily induced subgraphs of a given type, while in a subsequent paper we shall investigate the properties connected with counting induced subgraphs.Dedicated to the memory of Paul ErdsResearch supported by OTKA N1909.