首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 31 毫秒
1.
A matroidal family is a set F ≠ ? of connected finite graphs such that for every finite graph G the edge-sets of those subgraphs of G which are isomorphic to some element of F are the circuits of a matroid on the edge-set of G. Simões-Pereira [5] shows the existence of four matroidal families and Andreae [1] shows the existence of a countably infinite series of matroidal families. In this paper we show that there exist uncountably many matroidal families. This is done by using an extension of Andreae's theorem, a construction theorem, and certain properties of regular graphs. Moreover we observe that all matroidal families so far known can be obtained in a unified way.  相似文献   

2.
A matroidal family of graphs is a set M≠Ø of connected finite graphs such that for every finite graph G the edge sets of those subgraphs of G which are isomorphic to some element of M are the circuits of a matroid on the edge set of G. In [9], Schmidt shows that, for n?0, ?2n<r?1, n, r∈Z, the set M(n, r)={G∣G is a graph with β(G)=(G)+r and α(G )>, and is minimal with this property (with respect to the relation ?))} is a matroidal family of graphs. He also describes a method to construct new matroidal families of graphs by means of so-called partly closed sets. In this paper, an extension of this construction is given. By means of s-partly closed subsets of M(n, r), s?r, we are able to give sufficient and necessary conditions for a subset P(n, r) of M(n, r) to yield a matroidal family of graphs when joined with the set I(n, s) of all graphs G∈M(n, s) which satisfy: If H∈P(n, r), then H?G. In particular, it is shown that M(n, r) is not a matroidal family of graphs for r?2. Furthermore, for n?0, 1?2n<r, n, r∈Z, the set of bipartite elements of M(n, r) can be used to construct new matroidal families of graphs if and only if s?min(n+r, 1).  相似文献   

3.
A matroidal family C is defined to be a collection of graphs such that, for any given graph G, the subgraphs of G isomorphic to a graph in C satisfy the matroid circuit-axioms. Here matroidal families closed under homeomorphism are considered. A theorem of Simöes-Pereira shows that when only finite connected graphs are allowed as members of C, two matroids arise: the cycle matroid and bicircular matroid. Here this theorem is generalized in two directions: the graphs are allowed to be infinite, and they are allowed to be disconnected. In the first case four structures result and in the second case two infinite families of matroids are obtained. The main theorem concerns the structures resulting when both restrictions are relaxed simultaneously.  相似文献   

4.
An orthogonal latin square graph (OLSG) is one in which the vertices are latin squares of the same order and on the same symbols, and two vertices are adjacent if and only if the latin squares are orthogonal. If G is an arbitrary finite graph, we say that G is realizable as an OLSG if there is an OLSG isomorphic to G. The spectrum of G [Spec(G)] is defined as the set of all integers n that there is a realization of G by latin squares of order n. The two basic theorems proved here are (1) every graph is realizable and (2) for any graph G, Spec G contains all but a finite set of integers. A number of examples are given that point to a number of wide open questions. An example of such a question is how to classify the graphs for which a given n lies in the spectrum.  相似文献   

5.
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 xy in X, there exists S ∈ ?? with xS, 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.  相似文献   

6.
A graph L is called a link graph if there is a graph G such that for each vertex of G its neighbors induce a subgraph isomorphic to L. Such a G is said to have constant link .L Sabidussi proved that for any finite group F and any n ? 3 there are infinitely many n-regular connected graphs G with AutG ? Γ. We will prove a stronger result: For any finite group Γ and any link graph L with at least one isolated vertex and at least three vertices there are infinitely many connected graphs G with constant link L and AutG ? Γ.  相似文献   

7.
A perfect path double cover (PPDC) of a graph G on n vertices is a family ?? of n paths of G such that each edge of G belongs to exactly two members of ?? and each vertex of G occurs exactly twice as an end of a path of ??. We propose and study the conjecture that every simple graph admits a PPDC. Among other things, we prove that every simple 3-regular graph admits a PPDC consisting of paths of length three.  相似文献   

8.
For each positive integer n, let Tn be the tree in which exactly one vertex has degree n and all the other vertices have degree n + 1. A graph G is called stable if its edge set is nonempty and if deleting an arbitrary edge of G there is always a component of the residue graph which is isomorphic to G. The question whether there are locally finite stable graphs that are not isomorphic to one of the graphs Tn is answered affirmatively by constructing an uncountable family of pairwise nonisomorphic, locally finite, stable graphs. Further, the following results are proved: (1) Among the locally finite trees containing no subdivision of T2, the oneway infinite path T1 is the only stable graph. (2) Among the locally finite graphs containing no two-way infinite path, T1 is also the only stable graph.  相似文献   

9.
The R-set relative to a pair of distinct vertices of a connected graph G is the set of vertices whose distances to these vertices are distinct. This paper deduces some properties of R-sets of connected graphs. It is shown that for a connected graph G of order n and diameter 2 the number of R-sets equal to V(G) is bounded above by ?n2/4?{\lfloor n^{2}/4\rfloor} . It is conjectured that this bound holds for every connected graph of order n. A lower bound for the metric dimension dim(G) of G is proposed in terms of a family of R-sets of G having the property that every subfamily containing at least r ≥ 2 members has an empty intersection. Three sufficient conditions, which guarantee that a family F=(Gn)n 3 1{\mathcal{F}=(G_{n})_{n\geq 1}} of graphs with unbounded order has unbounded metric dimension, are also proposed.  相似文献   

10.
For every finite m and n there is a finite set {G1, …, Gl} of countable (m · Kn)-free graphs such that every countable (m · Kn)-free graph occurs as an induced subgraph of one of the graphs Gl © 1997 John Wiley & Sons, Inc.  相似文献   

11.
A graph G having a perfect matching is called n-extendable if every matching of size n of G can be extended to a perfect matching. In this note, we show that if G is an n-extendable nonbipartite graph, then G + e is (n - 1)-extendable for any edge e ? E(G). © 1992 John Wiley & Sons, Inc.  相似文献   

12.
We introduce a natural extension of the vertex degree to ends. For the cycle space C(G) as proposed by Diestel and Kühn [4, 5], which allows for infinite cycles, we prove that the edge set of a locally finite graph G lies in C(G) if and only if every vertex and every end has even degree. In the same way we generalise to locally finite graphs the characterisation of the cycles in a finite graph as its 2-regular connected subgraphs.  相似文献   

13.
An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a′(G). It was conjectured by Alon, Sudakov, and Zaks that for any simple and finite graph G, a′(G)?Δ + 2, where Δ=Δ(G) denotes the maximum degree of G. We prove the conjecture for connected graphs with Δ(G)?4, with the additional restriction that m?2n?1, where n is the number of vertices and m is the number of edges in G. Note that for any graph G, m?2n, when Δ(G)?4. It follows that for any graph G if Δ(G)?4, then a′(G)?7. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 192–209, 2009  相似文献   

14.
Let G be a finite group. The prime graph of G is a graph whose vertex set is the set of prime divisors of |G| and two distinct primes p and q are joined by an edge, whenever G contains an element of order pq. The prime graph of G is denoted by Γ(G). It is proved that some finite groups are uniquely determined by their prime graph. In this paper, we show that if G is a finite group such that Γ(G) = Γ(B n (5)), where n ? 6, then G has a unique nonabelian composition factor isomorphic to B n (5) or C n (5).  相似文献   

15.
The size Ramsey number r?(G, H) of graphs G and H is the smallest integer r? such that there is a graph F with r? edges and if the edge set of F is red-blue colored, there exists either a red copy of G or a blue copy of H in F. This article shows that r?(Tnd, Tnd) ? c · d2 · n and c · n3 ? r?(Kn, Tnd) ? c(d)·n3 log n for every tree Tnd on n vertices. and maximal degree at most d and a complete graph Kn on n vertices. A generalization will be given. Probabilistic method is used throught this paper. © 1993 John Wiley Sons, Inc.  相似文献   

16.
How few edge‐disjoint triangles can there be in a graph G on n vertices and in its complement ? This question was posed by P. Erd?s, who noticed that if G is a disjoint union of two complete graphs of order n/2 then this number is n2/12 + o(n2). Erd?s conjectured that any other graph with n vertices together with its complement should also contain at least that many edge‐disjoint triangles. In this paper, we show how to use a fractional relaxation of the above problem to prove that for every graph G of order n, the total number of edge‐disjoint triangles contained in G and is at least n2/13 for all sufficiently large n. This bound improves some earlier results. We discuss a few related questions as well. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 203–216, 2004  相似文献   

17.
An edge-deleted subgraph of a graph G is a subgraph obtained from G by the deletion of an edge. The Edge Reconstruction Conjecture asserts that every simple finite graph with four or more edges is determined uniquely, up to isomorphism, by its collection of edge-deleted subgraphs. A class of graphs is said to be edge reconstructible if there is no graph in the class with four or more edges that is not edge reconstructible. This paper proves that bidegreed graphs (graphs whose vertices all have one of two possible degrees) are edge reconstructible. The results are then generalized to show that all graphs that do not have three consecutive integers in their degree sequence are also edge reconstructible.  相似文献   

18.
In this article, we develop a theory of walks traversing every edge exactly twice. Rosenstiehl and Read proved that if G is a graph with no set of edges that is simultaneously a cycle and a cocycle, then G is planar if and only if there is a closed walk W in G traversing every edge exactly twice such that certain sets of edges derived from W are all cocycles. One consequence of the current work is a simple proof of the Rosenstiehl-Read theorem. Another is an unusual method for determining the rank (over the integers modulo 2) of a symmetric matrix obtained from a circle graph.  相似文献   

19.
A graph L is called a link graph if there is a graph G such that for each vertex of G its neighbors induce a subgraph isomorphic to L. Such a G is said to have constant link L. We prove that for any finite group Γ and any disconnected link graph L with at least three vertices there are infinitely many connected graphs G with constant link L and AutG ? Γ. We look at the analogous problem for connected link graphs, namely, link graphs that are paths or have disconnected complements. Furthermore we prove that for n, r ≥ 2, but not n = 2 = r, any finite group can be represented by infinitely many connected r-uniform, n-regular hypergraphs of arbitrarily large girth.  相似文献   

20.
A friendship graph is a graph in which every two distinct vertices have exactly one common neighbor. All finite friendship graphs are known, each of them consists of triangles having a common vertex. We extend friendship graphs to two-graphs, a two-graph being an ordered pair G = (G 0, G 1) of edge-disjoint graphs G 0 and G 1 on the same vertex-set V(G 0) = V(G 1). One may think that the edges of G are colored with colors 0 and 1. In a friendship two-graph, every unordered pair of distinct vertices u, v is connected by a unique bicolored 2-path. The pairs of adjacency matrices of friendship two-graphs are solutions to the matrix equation AB + BA = JI, where A and B are n × n symmetric 0 − 1 matrices, J is an n × n matrix with every entry being 1, and I is the identity n × n matrix. We show that there is no finite friendship two-graph with minimum vertex degree at most two. However, we construct an infinite such graph, and this construction can be extended to an infinite (uncountable) family. Also, we find a finite friendship two-graph, conjecture that it is unique, and prove this conjecture for the two-graphs that have a dominating vertex.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号