共查询到20条相似文献,搜索用时 31 毫秒
1.
Constructing cospectral graphs 总被引:1,自引:0,他引:1
Some new constructions for families of cospectral graphs are derived, and some old ones are considerably generalized. One of our new constructions is sufficiently powerful to produce an estimated 72% of the 51039 graphs on 9 vertices which do not have unique spectrum. In fact, the number of graphs of ordern without unique spectrum is believed to be at leastn
3
g
–1 for some>0, whereg
n is the number of graphs of ordern andn 7. 相似文献
2.
Noga Alon 《Combinatorica》1986,6(3):207-219
Expanding graphs are relevant to theoretical computer science in several ways. Here we show that the points versus hyperplanes
incidence graphs of finite geometries form highly (nonlinear) expanding graphs with essentially the smallest possible number
of edges. The expansion properties of the graphs are proved using the eigenvalues of their adjacency matrices.
These graphs enable us to improve previous results on a parallel sorting problem that arises in structural modeling, by describing
an explicit algorithm to sortn elements ink time units using
parallel processors, where, e.g., α2=7/4, α3=8/5, α4=26/17 and α5=22/15.
Our approach also yields several applications to Ramsey Theory and other extremal problems in combinatorics. 相似文献
3.
We construct an innite family of (q + 1)-regular Ramanujan graphs
X
n
of girth 1. We also give
covering maps X
n+1
X
n
such that the minimal
common covering of all the X
n
s is the universal
covering tree. 相似文献
4.
Let σ1,σ2 be two permutations in the symmetric group Sn. Among the many sequences of elementary transpositions τ1,…,τr transforming σ1 into σ2=τrτ1σ1, some of them may be signable, a property introduced in this paper. We show that the four color theorem in graph theory is equivalent to the statement that, for any n≥2 and any σ1,σ2Sn, there exists at least one signable sequence of elementary transpositions from σ1 to σ2. This algebraic reformulation rests on a former geometric one in terms of signed diagonal flips, together with a codification of the triangulations of a convex polygon on n+2 vertices by permutations in Sn. 相似文献
5.
Wolfgang Mader 《Combinatorica》2005,25(4):425-438
We determine all graphs on n ≥ 3 vertices with 3n-6 edges which do not contain a subdivision of K5. These are exactly the graphs which one gets from any number of disjoint maximal planar graphs by successively pasting along
triangles. 相似文献
6.
Ehud Hrushovski 《Combinatorica》1992,12(4):411-416
Theorem
Let X be a finite graph. Then there exists a finite graph Z containing X as an induced subgraphs, such that every isomorphism between induced subgraphs of X extends to an automorphism of Z.The graphZ may be required to be edge-transitive. The result implies that for anyn, there exists a notion of a genericn-tuple of automorphism of the Rado graphR (the random countable graph): for almost all automorphism 1,...,
n
and 1 ofR (in the sense of Baire category), (R,1,...,
n
), (R,1,...,
n
). The problem arose in a recent paper of Hodges, Hodgkinson, Lascar and Shelah, where the theorem is used to prove the small index property forR.Work supported by a Sloan Fellowship and by NSF grant DMS-8903378. 相似文献
7.
Let be a G-symmetric graph whose vertex set admits a nontrivial G-invariant partition with block size v. Let
be the quotient graph of relative to and [B,C] the bipartite subgraph of induced by adjacent blocks B,C of . In this paper we study such graphs for which
is connected, (G, 2)-arc transitive and is almost covered by in the sense that [B,C] is a matching of v-1 2 edges. Such graphs arose as a natural extremal case in a previous study by the author with Li and Praeger. The case
K
v+1 is covered by results of Gardiner and Praeger. We consider here the general case where
K
v+1, and prove that, for some even integer n 4,
is a near n-gonal graph with respect to a certain G-orbit on n-cycles of
. Moreover, we prove that every (G, 2)-arc transitive near n-gonal graph with respect to a G-orbit on n-cycles arises as a quotient
of a graph with these properties. (A near n-gonal graph is a connected graph of girth at least 4 together with a set of n-cycles of such that each 2-arc of is contained in a unique member of .) 相似文献
8.
M. Stiebitz 《Combinatorica》1987,7(3):303-312
Some problems and results on the distribution of subgraphs in colour-critical graphs are discussed.
In section 3 arbitrarily largek-critical graphs withn vertices are constructed such that, in order to reduce the chromatic number tok−2, at leastc
k
n
2 edges must be removed.
In section 4 it is proved that a 4-critical graph withn vertices contains at mostn triangles. Further it is proved that ak-critical graph which is not a complete graph contains a (k−1)-critical graph which is not a complete graph. 相似文献
9.
Elizabeth C.M. Maritz 《Quaestiones Mathematicae》2018,41(1):49-63
Let Π = {S1, S2, . . . , Sk} be an ordered partition of the vertex set V (G) of a graph G. The partition representation of a vertex v ∈ V (G) with respect to Π is the k-tuple r(v|Π) = (d(v, S1), d(v, S2), . . . , d(v, Sk)), where d(v, S) is the distance between v and a set S. If for every pair of distinct vertices u, v ∈ V (G), we have r(u|Π) ≠ r(v|Π), then Π is a resolving partition and the minimum cardinality of a resolving partition of V (G) is called the partition dimension of G. We study the partition dimension of circulant graphs, which are Cayley graphs of cyclic groups. Grigorious et al. [On the partition dimension of circulant graphs] proved that pd(Cn(1, 2, . . . , t)) ≥ t + 1 for n ≥ 3. We disprove this statement by showing that if t ≥ 4 is even, then there exists an infinite set of values of n, such that . We also present exact values of the partition dimension of circulant graphs with 3 generators. 相似文献
10.
On the full automorphism group of a graph 总被引:11,自引:0,他引:11
C. D. Godsil 《Combinatorica》1981,1(3):243-256
While it is easy to characterize the graphs on which a given transitive permutation groupG acts, it is very difficult to characterize the graphsX with Aut (X)=G. We prove here that for the certain transitive permutation groups a simple necessary condition is also sufficient. As a corollary
we find that, whenG is ap-group with no homomorphism ontoZ
p
wrZ
p
, almost all Cayley graphs ofG have automorphism group isomorphic toG. 相似文献
11.
What is the maximum possible number, f3(n), of vectors of length n over {0,1,2} such that the Hamming distance between every two is even? What is the maximum possible number, g3(n), of vectors in {0,1,2}n such that the Hamming distance between every two is odd? We investigate these questions, and more general ones, by studying
Xor powers of graphs, focusing on their independence number and clique number, and by introducing two new parameters of a
graph G. Both parameters denote limits of series of either clique numbers or independence numbers of the Xor powers of G (normalized appropriately), and while both limits exist, one of the series grows exponentially as the power tends to infinity,
while the other grows linearly. As a special case, it follows that f3(n) = Θ(2n) whereas g3(n)=Θ(n).
* Research supported in part by a USA-Israeli BSF grant, by the Israel Science Foundation and by the Hermann Minkowski Minerva
Center for Geometry at Tel Aviv University.
† Research partially supported by a Charles Clore Foundation Fellowship. 相似文献
12.
G. A. Margulis 《Combinatorica》1982,2(1):71-78
We give an explicit construction of regular graphs of degree 2r withn vertices and girth ≧c logn/logr. We use Cayley graphs of factor groups of free subgroups of the modular group. An application to low density codes is given. 相似文献
13.
Cunningham and Edmonds [4[ have proved that a 2-connected graphG has a unique minimal decomposition into graphs, each of which is either 3-connected, a bond or a polygon. They define the notion of a good split, and first prove thatG has a unique minimal decomposition into graphs, none of which has a good split, and second prove that the graphs that do not have a good split are precisely 3-connected graphs, bonds and polygons. This paper provides an analogue of the first result above for 3-connected graphs, and an analogue of the second for minimally 3-connected graphs. Following the basic strategy of Cunningham and Edmonds, an appropriate notion of good split is defined. The first main result is that ifG is a 3-connected graph, thenG has a unique minimal decomposition into graphs, none of which has a good split. The second main result is that the minimally 3-connected graphs that do not have a good split are precisely cyclically 4-connected graphs, twirls (K
3,n
for somen3) and wheels. From this it is shown that ifG is a minimally 3-connected graph, thenG has a unique minimal decomposition into graphs, each of which is either cyclically 4-connected, a twirl or a wheel.Research partially supported by Office of Naval Research Grant N00014-86-K-0689 at Purdue University. 相似文献
14.
Consider a compact Riemannian manifold (M, g) with metric g and dimension n ≥ 3. The Schouten tensor A
g
associated with g is a symmetric (0, 2)-tensor field describing the non-conformally-invariant part of the curvature tensor
of g. In this paper, we consider the elementary symmetric functions {σ
k
(A
g
), 1 ≤ k ≤ n} of the eigenvalues of A
g
with respect to g; we call σ
k
(A
g
) the k-th Schouten curvature function. We give an isometric classification for compact locally conformally flat manifolds which satisfy the conditions: A
g
is semi-positive definite and σ
k
(A
g
) is a nonzero constant for some k ∈ {2, ... , n}. If k = 2, we obtain a classification result under the weaker conditions that σ2(A
g
) is a non-negative constant and (M
n
, g) has nonnegative Ricci curvature. The corresponding result for the case k = 1 is well known. We also give an isometric classification for complete locally conformally flat manifolds with constant
scalar curvature and non-negative Ricci curvature.
Udo Simon: Partially supported by Chinese-German cooperation projects, DFG PI 158/4-4 and PI 158/4-5, and NSFC. 相似文献
15.
A graphG ismaximally nonhamiltonian iffG is not hamiltonian butG + e is hamiltonian for each edgee inG
c, i.e., any two non-adjacent vertices ofG are ends of a hamiltonian path. Bollobás posed the problem of finding the least number of edges,f(n), possible in a maximally nonhamiltonian graph of ordern. Results of Bondy show thatf(n) 3/2
n forn 7. We exhibit graphs of even ordern 36 for which the bound is attained. These graphs are the snarks,J
k, of Isaacs and mild variations of them. For oddn 55 we construct graphs from the graphsJ
k showing that in this case,f(n) = 3n + 1/2 or 3n + 3/2 and leave the determination of which is correct as an open problem. Finally we note that the graphsJ
k, k 7 are hypohamiltonian cubics with girth 6. 相似文献
16.
This paper studies a number of problems on cycle-free partial orders and chordal comparability graphs. The dimension of a cycle-free partial order is shown to be at most 4. A linear time algorithm is presented for determining whether a chordal directed graph is transitive, which yields an O(n
2) algorithm for recognizing chordal comparability graphs. An algorithm is presented for determining whether the transitive closure of a digraph is a cycle-free partial order in O(n+m
t)time, where m
tis the number of edges in the transitive closure. 相似文献
17.
Dieter Rautenbach 《Discrete Mathematics》2008,308(11):2325-2329
Let G be a graph of order n, minimum degree δ?2, girth g?5 and domination number γ. In 1990 Brigham and Dutton [Bounds on the domination number of a graph, Q. J. Math., Oxf. II. Ser. 41 (1990) 269-275] proved that γ?⌈n/2-g/6⌉. This result was recently improved by Volkmann [Upper bounds on the domination number of a graph in terms of diameter and girth, J. Combin. Math. Combin. Comput. 52 (2005) 131-141; An upper bound for the domination number of a graph in terms of order and girth, J. Combin. Math. Combin. Comput. 54 (2005) 195-212] who for i∈{1,2} determined a finite set of graphs Gi such that γ?⌈n/2-g/6-(3i+3)/6⌉ unless G is a cycle or G∈Gi.Our main result is that for every i∈N there is a finite set of graphs Gi such that γ?n/2-g/6-i unless G is a cycle or G∈Gi. Furthermore, we conjecture another improvement of Brigham and Dutton's bound and prove a weakened version of this conjecture. 相似文献
18.
MENGJIXIANG DONGYALI 《高校应用数学学报(英文版)》1996,11(2):239-242
Abstract. We prove that the cyclic group Zn(n≥3) has a k-regular digraph regular 相似文献
19.
Dezső Miklós 《Combinatorica》1992,12(3):367-369
In his thesis [3] B. D. Thatte conjectured that ifG=G
1,G
2,...G
n
is a sequence of finitely many simple connected graphs (isomorphic graphs may occur in the sequence) with the same number of vertices and edges then their shuffled edge deck uniquely determines the graph sequence (up to a permutation). In this paper we prove that there are such sequences of graphs with the same shuffled edge deck.This research was partially supported by Hungarian National Foundation of Scientific Research Grant no. 1812 相似文献
20.
The local tree-width of
a graph G=(V,E) is the function
ltwG : that associates
with every r the maximal
tree-width of an r-neighborhood in
G. Our main grapht heoretic
result is a decomposition theorem for graphs with excluded
minors, which says that such graphs can be decomposed into trees
of graphs of almost bounded local tree-width.As an application of this theorem, we show that a number
of combinatorial optimization problems, suchas
Minimum Vertex Cover,
Minimum Dominating Set,
and Maximum Independent
Set have a polynomial time approximation scheme when
restricted to a class of graphs with an excluded minor. 相似文献