A note on regular Ramsey graphs

We prove that there is an absolute constant C>0 so that for every natural n there exists a triangle‐free regular graph with no independent set of size at least \({{C}}\sqrt{{{n}}\log{{n}}}\). © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 244–249, 2010     

Disconnecting strongly regular graphs

In this paper, we show that the minimum number of vertices whose removal disconnects a connected strongly regular graph into non-singleton components equals the size of the neighborhood of an edge for many graphs. These include block graphs of Steiner 2-designs, many Latin square graphs and strongly regular graphs whose intersection parameters are at most a quarter of their valency.     

A geometrical characterization of strongly regular graphs

We give a necessary and sufficient condition of a Euclidean representation of a simple graph to be spherical. Moreover we show a characterization of strongly regular graphs from the view point of Euclidean representations of a graph. From this characterization, we define a natural generalized concept of a strongly regular graph closely related to Euclidean designs and codes.     

On strongly almost trivial embeddings of graphs

We present four new classes of graphs, two of which every member has a strongly almost trivial embedding, and the other two of which every member has no strongly almost trivial embeddings. We show that the property that a graph has a strongly almost trivial embedding and the property that a graph has no strongly almost trivial embeddings are not inherited by minors. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory     

Classification of reflexible regular embeddings and self-Petrie dual regular embeddings of complete bipartite graphs

In this paper, we classify the reflexible regular orientable embeddings and the self-Petrie dual regular orientable embeddings of complete bipartite graphs. The classification shows that for any natural number n, say (p₁,p₂,…,p_k are distinct odd primes and a_i>0 for each i?1), there are t distinct reflexible regular embeddings of the complete bipartite graph K_n,n up to isomorphism, where t=1 if a=0, t=2^k if a=1, t=2^k+1 if a=2, and t=3·2^k+1 if a?3. And, there are s distinct self-Petrie dual regular embeddings of K_n,n up to isomorphism, where s=1 if a=0, s=2^k if a=1, s=2^k+1 if a=2, and s=2^k+2 if a?3.     

Some new strongly regular graphs

We show that three pairwise 4-regular graphs constructed by the second author are members of infinite families.     

5-chromatic strongly regular graphs

In this paper, we begin the determination of all primitive strongly regular graphs with chromatic number equal to 5. Using eigenvalue techniques, we show that there are at most 43 possible parameter sets for such a graph. For each parameter set, we must decide which strongly regular graphs, if any, possessing the set are 5-chromatic. In this way, we deal completely with 34 of these parameter sets using eigenvalue techniques and computer enumerations.     

Nonorientable regular embeddings of graphs of order pq

In [J. Algeb. Combin. 19(2004), 123-141], Du et al. classified the orientable regular embeddings of connected simple graphs of order pq for any two primes p and q. In this paper, we shall classify the nonorientable regular embeddings of these graphs, where p ≠ q. Our classification depends on the classification of primitive permutation groups of degree p and degree pq but is independent of the classification of the arc-transitive graphs of order pq.     

Forest embeddings in regular graphs of large girth

This paper deals with the enumeration of distinct embeddings (both induced and partial) of arbitrary graphs in regular graphs of large girth. A simple explicit recurrence formula is presented for the number of embeddings of an arbitrary forest F in an arbitrary regular graph G of sufficiently large girth. This formula (and hence the number of embeddings) depends only on the order and degree of regularity of G, and the degree sequence and component structure (multiset of component orders) of F. A concept called c-subgraph regularity is introduced which generalizes the familiar notion of regularity in graphs. (Informally, a graph is c-subgraph regular if its vertices cannot be distinguished on the basis of embeddings of graphs of order less than or equal to c.) A central result of this paper is that if G is regular and has girth g, then G is (g ? 1)-subgraph regular.     

New families of strongly regular graphs

We apply symmetric balanced generalized weighing matrices with zero diagonal to construct four parametrically new infinite families of strongly regular graphs. © 2003 Wiley Periodicals, Inc. J Combin Designs 11: 208–217, 2003; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10038     

A note on bipartite subgraphs of triangle-free regular graphs

Lower bounds on the size of a maximum bipartite subgraph of a triangle-free r-regular graph are presented.     

A note on strong embeddings of maximal planar graphs on non-orientable sufraces

Abstract. In this paper, it is shown that for every maximal planar graph     

A characterization of two classes of strongly regular graphs

The half dual polar graphsD _4,4(q) and the alternating forms graphsAlt(4,q) are characterized among strongly regular graphs with classical parameters via the geometric structures of polar spaces and affine polar spaces of rank 4, respectively.     

A generalization of Wallis-Fon-Der-Flaass construction of strongly regular graphs

In this paper the Wallis-Fon-Der-Flaass construction of strongly regular graphs is generalized. As a result new prolific series of strongly regular graphs are obtained. Some of them have new parameters. The author was partially supported by the Israeli Ministry of Absorption.     

A note on rainbow matchings in strongly edge-colored graphs

The Ryser Conjecture which states that there is a transversal of size $n$ in a Latin square of odd order $n$ is equivalent to finding a rainbow matching of size $n$ in a properly edge-colored $K_{n,n}$ using $n$ colors when $n$ is odd. Let $\delta$ be the minimum degree of a graph. Wang proposed a more general question to find a function $f\left(\delta \right)$ such that every properly edge-colored graph of order $f\left(\delta \right)$ contains a rainbow matching of size $\delta$, which currently has the best bound of $f\left(\delta \right)\le 3.5\delta +2$ by Lo. Babu, Chandran and Vaidyanathan investigated Wang’s question under a stronger color condition. A strongly edge-colored graph is a properly edge-colored graph in which every monochromatic subgraph is an induced matching. Wang, Yan and Yu proved that every strongly edge-colored graph of order at least $2\delta +2$ has a rainbow matching of size $\delta$. In this note, we extend this result to graphs of order at least $2\delta +1$.