共查询到20条相似文献,搜索用时 15 毫秒
1.
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 相似文献
2.
3.
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. 相似文献
4.
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. 相似文献
5.
Ryo Hanaki 《Journal of Graph Theory》2012,70(1):67-79
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 相似文献
6.
Jin Ho Kwak 《Discrete Mathematics》2008,308(11):2156-2166
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 (p1,p2,…,pk are distinct odd primes and ai>0 for each i?1), there are t distinct reflexible regular embeddings of the complete bipartite graph Kn,n up to isomorphism, where t=1 if a=0, t=2k if a=1, t=2k+1 if a=2, and t=3·2k+1 if a?3. And, there are s distinct self-Petrie dual regular embeddings of Kn,n up to isomorphism, where s=1 if a=0, s=2k if a=1, s=2k+1 if a=2, and s=2k+2 if a?3. 相似文献
7.
We show that three pairwise 4-regular graphs constructed by the second author are members of infinite families. 相似文献
8.
Nick C. Fiala 《Discrete Mathematics》2006,306(23):3083-3096
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. 相似文献
9.
WANG FuRong & DU ShaoFei School of Information Beijing Wuzi University Beijing China School of Mathematical Sciences Capital Normal University Beijing 《中国科学 数学(英文版)》2011,(2)
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. 相似文献
10.
11.
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. 相似文献
12.
13.
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 相似文献
14.
S. C. Locke 《Journal of Graph Theory》1990,14(2):181-185
Lower bounds on the size of a maximum bipartite subgraph of a triangle-free r-regular graph are presented. 相似文献
15.
LiuTongyin LiuYanpei 《高校应用数学学报(英文版)》2001,16(2):111-114
Abstract. In this paper, it is shown that for every maximal planar graph 相似文献
16.
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. 相似文献
17.
Mikhail Muzychuk 《Journal of Algebraic Combinatorics》2007,25(2):169-187
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. 相似文献
18.
19.
20.
The Ryser Conjecture which states that there is a transversal of size in a Latin square of odd order is equivalent to finding a rainbow matching of size in a properly edge-colored using colors when is odd. Let be the minimum degree of a graph. Wang proposed a more general question to find a function such that every properly edge-colored graph of order contains a rainbow matching of size , which currently has the best bound of 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 has a rainbow matching of size . In this note, we extend this result to graphs of order at least . 相似文献