共查询到20条相似文献,搜索用时 15 毫秒
1.
2.
It is shown that transitive 1-factorizations of arc-transitive graphs exist if and only if certain factorizations of their automorphism groups exist. This relation provides a method for constructing and characterizing transitive 1-factorizations for certain classes of arc-transitive graphs. Then a characterization is given of 2-arc-transitive graphs which have transitive 1-factorizations. In this characterization, some 2-arc transitive graphs and their transitive 1-factorizations are constructed. 相似文献
3.
In Korchmáros et al. (2018)one-factorizations of the complete graph are constructed for with any odd prime power such that either or . The arithmetic restriction is due to the fact that the vertices of in the construction are the points of a conic in the finite plane of order . Here we work on the Euclidean plane and describe an analogous construction where the role of is taken by a regular -gon. This allows us to remove the above constraints and construct one-factorizations of for every even . 相似文献
4.
5.
J. D. Horton 《Aequationes Mathematicae》1981,22(1):56-63
The existence of a Room square of order 2n is known to be equivalent to the existence of two orthogonal one-factorizations of the complete graph on 2n vertices, where orthogonal means any two one-factors involved have at most one edge in common. DefineR(n) to be the maximal number of pairwise orthogonal one-factorizations of the complete graph onn vertices.The main results of this paper are bounds on the functionR. If there is a strong starter of order 2n–1 thenR(2n) 3. If 4n–1 is a prime power, it is shown thatR(4n) 2n–1. Also, the recursive construction for Room squares, to obtain, a Room design of sidev(u – w) +w from a Room design of sidev and a Room design of sideu with a subdesign of sidew, is generalized to sets ofk pairwise orthogonal factorizations. It is further shown thatR(2n) 2n–3. 相似文献
6.
A. Gerbaud 《Discrete Mathematics》2010,310(21):2824-2830
We compute the Laplacian spectra and eigenfunctions of generalized compositions of graphs, as explicit functions of the spectra and eigenfunctions of their components. Applications to two-level hierarchical graphs are given. We introduce the tree composition of graphs and study its spectral decomposition, with applications to some hierarchical networks. 相似文献
7.
8.
9.
10.
For an integer , a graph is -hamiltonian if for any vertex subset with , is hamiltonian, and is -hamiltonian connected if for any vertex subset with , is hamiltonian connected. Thomassen in 1984 conjectured that every 4-connected line graph is hamiltonian (see Thomassen, 1986), and Ku?zel and Xiong in 2004 conjectured that every 4-connected line graph is hamiltonian connected (see Ryjá?ek and Vrána, 2011). In Broersma and Veldman (1987), Broersma and Veldman raised the characterization problem of -hamiltonian line graphs. In Lai and Shao (2013), it is conjectured that for , a line graph is -hamiltonian if and only if is -connected. In this paper we prove the following.(i) For an integer , the line graph of a claw-free graph is -hamiltonian if and only if is -connected.(ii) The line graph of a claw-free graph is 1-hamiltonian connected if and only if is 4-connected. 相似文献
11.
We enumerate the nonisomorphic and the distinct one-factorizations of K12. We also describe the algorithm used to obtain the result, and the methods we used to verify these numbers. © 1994 John Wiley & Sons, Inc. 相似文献
12.
Chong-Keang Lim 《Journal of Graph Theory》1978,2(4):349-355
A graph G is called a supercompact graph if G is the intersection graph of some family ?? of subsets of a set X such that ?? satisfies the Helly property and for any x≠y in X, there exists S ∈ ?? with x ∈ S, y ? S. Various characterizations of supercompact graphs are given. It is shown that every clique-critical graph is supercompact. Furthermore, for any finite graph, H, there is at most a finite number of different supercompact graphs G such that H is the clique-graph of G. 相似文献
13.
Chvátal defined a graph G to be brittle if each induced subgraph F of G contains a vertex that is not a midpoint of any P4 or not an endpoint of any P4. Every brittle graph is perfectly orderable. In this paper, we prove that a graph is brittle whenever it is HHD-free (containing no chordless cycle with at least five vertices, no cycle on six vertices with a long chord, and no complement of the chordless path on five vertices). We also design an O(n4) algorithm to recognize HHD-free graphs, and also an O(n4) algorithm to construct a perfect order of an HHD-free graph. It follows from this result that an optimal coloring and a largest clique of an HHD-free graph can be found in O(n4) time. 相似文献
14.
It is frequently of interest to represent a given graph G as a subgraph of a graph H which has some special structure. A particularly useful class of graphs in which to embed G is the class of n-dimensional cubes. This has found applications, for example, in coding theory, data transmission, and linguistics. In this note, we study the structure of those graphs G, called cubical graphs (not to be confused with cubic graphs, those graphs for which all vertices have degree 3), which can be embedded into an n-dimensional cube. A basic technique used is the investigation of graphs which are critically nonembeddable, i.e., which can not be embedded but all of whose subgraphs can be embedded. 相似文献
15.
We give an upper bound of the number of edges of a permutation graph. We introduce some necessary conditions for a graph to be a permutation graph, and we discuss the independence of these necessary conditions. We show that they are altogether not sufficient for a graph to be a permutation graph. 相似文献
16.
Chiara Epifanio 《Discrete Applied Mathematics》2007,155(8):1014-1030
In this paper we define Sturmian graphs and we prove that all of them have a certain “counting” property. We show deep connections between this counting property and two conjectures, by Moser and by Zaremba, on the continued fraction expansion of real numbers. These graphs turn out to be the underlying graphs of compact directed acyclic word graphs of central Sturmian words. In order to prove this result, we give a characterization of the maximal repeats of central Sturmian words. We show also that, in analogy with the case of Sturmian words, these graphs converge to infinite ones. 相似文献
17.
How many edges can be in a graph which is forced to be contained in every graph onn vertices ande edges? In this paper we obtain bounds which are in many cases asymptotically best possible. 相似文献
18.
Kenjiro Ogawa 《Discrete Mathematics》2010,310(22):3276-3277
For a poset P=(X,≤), the upper bound graph (UB-graph) of P is the graph U=(X,EU), where uv∈EU if and only if u≠v and there exists m∈X such that u,v≤m. For a graph G, the distance two graph DS2(G) is the graph with vertex set V(DS2(G))=V(G) and u,v∈V(DS2(G)) are adjacent if and only if dG(u,v)=2. In this paper, we deal with distance two graphs of upper bound graphs. We obtain a characterization of distance two graphs of split upper bound graphs. 相似文献
19.
Sachin Gautam Ashish Kumar Srivastava Amitabha Tripathi 《Discrete Applied Mathematics》2008,156(12):2423-2428
Given graphs , where k≥2, the notation
20.
P. Erdös 《Israel Journal of Mathematics》1964,2(3):183-190
Anr-graph is a graph whose basic elements are its vertices and r-tuples. It is proved that to everyl andr there is anε(l, r) so that forn>n
0 everyr-graph ofn vertices andn
r−ε(l, r) r-tuples containsr. l verticesx
(j), 1≦j≦r, 1≦i≦l, so that all ther-tuples
occur in ther-graph. 相似文献