共查询到20条相似文献,搜索用时 31 毫秒
1.
Let G be a graph on the vertex set V={x
1, ..., x
n}. Let k be a field and let R be the polynomial ring k[x
1, ..., x
n]. The graph ideal
I(G), associated to G, is the ideal of R generated by the set of square-free monomials x
ixj so that x
i, is adjacent to x
j. The graph G is Cohen-Macaulay over k if R/I(G) is a Cohen-Macaulay ring.
Let G be a Cohen-Macaulay bipartite graph. The main result of this paper shows that G{v} is Cohen-Macaulay for some vertex v in G. Then as a consequence it is shown that the Reisner-Stanley simplicial complex of I(G) is shellable. An example of N. Terai is presented showing these results fail for Cohen-Macaulay non bipartite graphs.
Partially supported by COFAA-IPN, CONACyT and SNI, México. 相似文献
2.
Ting-Chung Chang 《Linear algebra and its applications》2011,435(10):2451-2461
By the signless Laplacian of a (simple) graph G we mean the matrix Q(G)=D(G)+A(G), where A(G),D(G) denote respectively the adjacency matrix and the diagonal matrix of vertex degrees of G. For every pair of positive integers n,k, it is proved that if 3?k?n-3, then Hn,k, the graph obtained from the star K1,n-1 by joining a vertex of degree 1 to k+1 other vertices of degree 1, is the unique connected graph that maximizes the largest signless Laplacian eigenvalue over all connected graphs with n vertices and n+k edges. 相似文献
3.
choice number of a graph G is the minimum integer k such that for every assignment of a set S(v) of k colors to every vertex v of G, there is a proper coloring of G that assigns to each vertex v a color from S(v). It is shown that the choice number of the random graph G(n, p(n)) is almost surely whenever . A related result for pseudo-random graphs is proved as well. By a special case of this result, the choice number (as well
as the chromatic number) of any graph on n vertices with minimum degree at least in which no two distinct vertices have more than common neighbors is at most .
Received: October 13, 1997 相似文献
4.
C. D. Godsil 《Combinatorica》1981,1(4):369-376
Ak-matching in a graphG is a set ofk edges, no two of which have a vertex in common. The number of these inG is writtenp(G, k). Using an idea due to L. H. Harper, we establish a condition under which these numbers are approximately normally distributed.
We show that our condition is satisfied ifn=|V(G)| is large compared to the maximum degree Δ of a vertex inG(i.e. Δ=o(n)) orG is a large complete graph. One corollary of these results is that the number of points fixed by a randomly chosen involution
in the symmetric groupS is asymptotically normally distributed. 相似文献
5.
We say that H has an odd complete minor of order at least l if there are l vertex disjoint trees in H such that every two of them are joined by an edge, and in addition, all the vertices of trees are two-colored in such a way that the edges within the trees are bichromatic, but the edges between trees are monochromatic. Gerards and Seymour conjectured that if a graph has no odd complete minor of order l, then it is (l ? 1)-colorable. This is substantially stronger than the well-known conjecture of Hadwiger. Recently, Geelen et al. proved that there exists a constant c such that any graph with no odd K k -minor is ck√logk-colorable. However, it is not known if there exists an absolute constant c such that any graph with no odd K k -minor is ck-colorable. Motivated by these facts, in this paper, we shall first prove that, for any k, there exists a constant f(k) such that every (496k + 13)-connected graph with at least f(k) vertices has either an odd complete minor of size at least k or a vertex set X of order at most 8k such that G–X is bipartite. Since any bipartite graph does not contain an odd complete minor of size at least three, the second condition is necessary. This is an analogous result of Böhme et al. We also prove that every graph G on n vertices has an odd complete minor of size at least n/2α(G) ? 1, where α(G) denotes the independence number of G. This is an analogous result of Duchet and Meyniel. We obtain a better result for the case α(G)= 3. 相似文献
6.
T. Bartnicki 《Discrete Mathematics》2008,308(8):1388-1393
Using a fixed set of colors C, Ann and Ben color the edges of a graph G so that no monochromatic cycle may appear. Ann wins if all edges of G have been colored, while Ben wins if completing a coloring is not possible. The minimum size of C for which Ann has a winning strategy is called the game arboricity of G, denoted by Ag(G). We prove that Ag(G)?3k for any graph G of arboricity k, and that there are graphs such that Ag(G)?2k-2. The upper bound is achieved by a suitable version of the activation strategy, used earlier for the vertex coloring game. We also provide two other strategies based on induction and acyclic colorings. 相似文献
7.
《Quaestiones Mathematicae》2013,36(3):339-348
Abstract For n a positive integer and v a vertex of a graph G, the nth order degree of v in G, denoted by degnv, is the number of vertices at distance n from v. The graph G is said to be nth order regular of degree k if, for every vertex v of G, degnv = k. The following conjecture due to Alavi, Lick, and Zou is proved: For n ≥ 2, if G is a connected nth order regular graph of degree 1, then G is either a path of length 2n—1 or G has diameter n. Properties of nth order regular graphs of degree k, k ≥ 1, are investigated. 相似文献
8.
Sheng Bau 《Quaestiones Mathematicae》2018,41(4):541-548
We show that if G is a 3-connected graph of minimum degree at least 4 and with |V (G)| ≥ 7 then one of the following is true: (1) G has an edge e such that G/e is a 3-connected graph of minimum degree at least 4; (2) G has two edges uv and xy with ux, vy, vx ∈ E(G) such that the graph G/uv/xy obtained by contraction of edges uv and xy in G is a 3-connected graph of minimum degree at least 4; (3) G has a vertex x with N(x) = {x1, x2, x3, x4} and x1x2, x3x4 ∈ E(G) such that the graph (G ? x)/x1x2/x3x4 obtained by contraction of edges x1x2 and x3x4 in G – x is a 3-connected graph of minimum degree at least 4.Each of the three reductions is necessary: there exists an infinite family of 3- connected graphs of minimum degree not less than 4 such that only one of the three reductions may be performed for the members of the family and not the two other reductions. 相似文献
9.
Stephen G. Hartke 《Discrete Applied Mathematics》2006,154(11):1633-1639
Given an acyclic digraph D, the competition graph C(D) is defined to be the undirected graph with V(D) as its vertex set and where vertices x and y are adjacent if there exists another vertex z such that the arcs (x,z) and (y,z) are both present in D. The competition number k(G) for an undirected graph G is the least number r such that there exists an acyclic digraph F on |V(G)|+r vertices where C(F) is G along with r isolated vertices. Kim and Roberts [The Elimination Procedure for the Competition Number, Ars Combin. 50 (1998) 97-113] introduced an elimination procedure for the competition number, and asked whether the procedure calculated the competition number for all graphs. We answer this question in the negative by demonstrating a graph where the elimination procedure does not calculate the competition number. This graph also provides a negative answer to a similar question about the related elimination procedure for the phylogeny number introduced by the current author in [S.G. Hartke, The Elimination Procedure for the Phylogeny Number, Ars Combin. 75 (2005) 297-311]. 相似文献
10.
Claude Berge 《Combinatorica》1982,2(3):213-222
Gallai and Milgram have shown that the vertices of a directed graph, with stability number α(G), can be covered by exactly α(G) disjoint paths. However, the various proofs of this result do not imply the existence of a maximum stable setS and of a partition of the vertex-set into paths μ1, μ2, ..., μk such tht |μi ∩S|=1 for alli.
Later, Gallai proved that in a directed graph, the maximum number of vertices in a path is at least equal to the chromatic
number; here again, we do not know if there exists an optimal coloring (S
1,S
2, ...,S
k) and a path μ such that |μ ∩S
i|=1 for alli.
In this paper we show that many directed graphs, like the perfect graphs, have stronger properties: for every maximal stable
setS there exists a partition of the vertex set into paths which meet the stable set in only one point. Also: for every optimal
coloring there exists a path which meets each color class in only one point. This suggests several conjecties similar to the
perfect graph conjecture.
Dedicated to Tibor Gallai on his seventieth birthday 相似文献
11.
A graph G with no isolated vertex is total domination vertex critical if for any vertex v of G that is not adjacent to a vertex of degree one, the total domination number of G-v is less than the total domination number of G. These graphs we call γt-critical. If such a graph G has total domination number k, we call it k-γt-critical. We characterize the connected graphs with minimum degree one that are γt-critical and we obtain sharp bounds on their maximum diameter. We calculate the maximum diameter of a k-γt-critical graph for k?8 and provide an example which shows that the maximum diameter is in general at least 5k/3-O(1). 相似文献
12.
Xuding Zhu 《Journal of Graph Theory》2005,48(3):210-218
This paper discusses the circular version of list coloring of graphs. We give two definitions of the circular list chromatic number (or circular choosability) χc, l(G) of a graph G and prove that they are equivalent. Then we prove that for any graph G, χc, l(G) ≥ χl(G) ? 1. Examples are given to show that this bound is sharp in the sense that for any ? 0, there is a graph G with χc, l(G) > χl(G) ? 1 + ?. It is also proved that k‐degenerate graphs G have χc, l(G) ≤ 2k. This bound is also sharp: for each ? < 0, there is a k‐degenerate graph G with χc, l(G) ≥ 2k ? ?. This shows that χc, l(G) could be arbitrarily larger than χl(G). Finally we prove that if G has maximum degree k, then χc, l(G) ≤ k + 1. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 210–218, 2005 相似文献
13.
《Quaestiones Mathematicae》2013,36(2):159-164
AbstractThe Steiner distance d(S) of a set S of vertices in a connected graph G is the minimum size of a connected subgraph of G that contains S. The Steiner number s(G) of a connected graph G of order p is the smallest positive integer m for which there exists a set S of m vertices of G such that d(S) = p—1. A smallest set S of vertices of a connected graph G of order p for which d(S) = p—1 is called a Steiner spanning set of G. It is shown that every connected graph has a unique Steiner spanning set. If G is a connected graph of order p and k is an integer with 0 ≤ k ≤ p—1, then the kth Steiner number sk(G) of G is the smallest positive integer m for which there exists a set S of m vertices of G such that d(S) = k. The sequence so(G),s1 (G),…,8p-1(G) is called the Steiner sequence of G. Steiner sequences for trees are characterized. 相似文献
14.
A graph G is k-linked if G has at least 2k vertices, and for any 2k vertices x
1,x
2, …, x
k
,y
1,y
2, …, y
k
, G contains k pairwise disjoint paths P
1, …, P
k
such that P
i
joins x
i
and y
i
for i = 1,2, …, k. We say that G is parity-k-linked if G is k-linked and, in addition, the paths P
1, …, P
k can be chosen such that the parities of their length are prescribed. Thomassen [22] was the first to prove the existence
of a function f(k) such that every f(k)-connected graph is parity-k-linked if the deletion of any 4k-3 vertices leaves a nonbipartite graph.
In this paper, we will show that the above statement is still valid for 50k-connected graphs. This is the first result that connectivity which is a linear function of k guarantees the Erdős-Pósa type result for parity-k-linked graphs.
Research partly supported by the Japan Society for the Promotion of Science for Young Scientists, by Japan Society for the
Promotion of Science, Grant-in-Aid for Scientific Research and by Inoue Research Award for Young Scientists. 相似文献
15.
《Quaestiones Mathematicae》2013,36(3-4):235-245
Abstract Let G be a graph and let v be a vertex of G. The open neigbourhood N(v) of v is the set of all vertices adjacent with v in G. An open packing of G is a set of vertices whose open neighbourhoods are pairwise disjoint. The lower open packing number of G, denoted ρ° L(G), is the minimum cardinality of a maximal open packing of G while the (upper) open packing number of G, denoted ρ°(G), is the maximum cardinality among all open packings of G. It is known (see [7]) that if G is a connected graph of order n ≥3, then ρ°(G) ≤ 2n/3 and this bound is sharp (even for trees). As a consequence of this result, we know that ρ° L(G) ≤ 2n/3. In this paper, we improve this bound when G is a tree. We show that if G is a tree of order n with radius 3, then ρ° L(G) ≤ n/2 + 2 √n-1, and this bound is sharp, while if G is a tree of order n with radius at least 4, then ρ° L(G) is bounded above by 2n/3—O√n). 相似文献
16.
An equitable coloring of a graph is a proper vertex coloring such that the sizes of any two color classes differ by at most one. The least positive integer k for which there exists an equitable coloring of a graph G with k colors is said to be the equitable chromatic number of G and is denoted by χ=(G). The least positive integer k such that for any k′ ≥ k there exists an equitable coloring of a graph G with k′ colors is said to be the equitable chromatic threshold of G and is denoted by χ=*(G). In this paper, we investigate the asymptotic behavior of these coloring parameters in the probability space G(n,p) of random graphs. We prove that if n?1/5+? < p < 0.99 for some 0 < ?, then almost surely χ(G(n,p)) ≤ χ=(G(n,p)) = (1 + o(1))χ(G(n,p)) holds (where χ(G(n,p)) is the ordinary chromatic number of G(n,p)). We also show that there exists a constant C such that if C/n < p < 0.99, then almost surely χ(G(n,p)) ≤ χ=(G(n,p)) ≤ (2 + o(1))χ(G(n,p)). Concerning the equitable chromatic threshold, we prove that if n?(1??) < p < 0.99 for some 0 < ?, then almost surely χ(G(n,p)) ≤ χ=* (G(n,p)) ≤ (2 + o(1))χ(G(n,p)) holds, and if < p < 0.99 for some 0 < ?, then almost surely we have χ(G(n,p)) ≤ χ=*(G(n,p)) = O?(χ(G(n,p))). © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009 相似文献
17.
A graph G homogeneously embeds in a graph H if for every vertex x of G and every vertex y of H there is an induced copy of G in H with x at y. The graph G uniformly embeds in H if for every vertex y of H there is an induced copy of G in H containing y. For positive integer k, let fk(G) (respectively, gk(G)) be the minimum order of a graph H whose edges can be k-coloured such that for each colour, G homogeneously embeds (respectively, uniformly embeds) in the graph given by V(H) and the edges of that colour. We investigate the values f2(G) and g2(G) for special classes of G, in particular when G is a star or balanced complete bipartite graph. Then we investigate fk(G) and gk(G) when k ≥ 3 and G is a complete graph. 相似文献
18.
Li-Da Tong 《Discrete Applied Mathematics》2008,156(10):1838-1845
Let D be a connected oriented graph. A set S⊆V(D) is convex in D if, for every pair of vertices x,y∈S, the vertex set of every x-y geodesic (x-y shortest dipath) and y-x geodesic in D is contained in S. The convexity numbercon(D) of a nontrivial oriented graph D is the maximum cardinality of a proper convex set of D. Let G be a graph. We define that SC(G)={con(D):D is an orientation of G} and SSC(G)={con(D):D is a strongly connected orientation of G}. In the paper, we show that, for any n?4, 1?a?n-2, and a≠2, there exists a 2-connected graph G with n vertices such that SC(G)=SSC(G)={a,n-1} and there is no connected graph G of order n?3 with SSC(G)={n-1}. Then, we determine that SC(K3)={1,2}, SC(K4)={1,3}, SSC(K3)=SSC(K4)={1}, SC(K5)={1,3,4}, SC(K6)={1,3,4,5}, SSC(K5)=SSC(K6)={1,3}, SC(Kn)={1,3,5,6,…,n-1}, SSC(Kn)={1,3,5,6,…,n-2} for n?7. Finally, we prove that, for any integers n, m, and k with , 1?k?n-1, and k≠2,4, there exists a strongly connected oriented graph D with n vertices, m edges, and convexity number k. 相似文献
19.
Non-Separating Paths in 4-Connected Graphs 总被引:2,自引:0,他引:2
In 1975, Lovász conjectured that for any positive integer k, there exists a minimum positive integer f(k) such that, for any two vertices x, y in any f(k)-connected graph G, there is a path P from x to y in G such that G–V(P) is k-connected. A result of Tutte implies f(1) = 3. Recently, f(2) = 5 was shown by Chen et al. and, independently, by Kriesell. In this paper, we show that f(2) = 4 except for double wheels.Received October 17, 2003 相似文献
20.
The k-th power of a graph G is the graph whose vertex set is V(G)
k
, where two distinct k-tuples are adjacent iff they are equal or adjacent in G in each coordinate. The Shannon capacity of G, c(G), is lim
k→∞
α(G
k
)1/k
, where α(G) denotes the independence number of G. When G is the characteristic graph of a channel C, c(G) measures the effective alphabet size of C in a zero-error protocol. A sum of channels, C = Σ
i
C
i
, describes a setting when there are t ≥ 2 senders, each with his own channel C
i
, and each letter in a word can be selected from any of the channels. This corresponds to a disjoint union of the characteristic
graphs, G = Σ
i
G
i
. It is well known that c(G) ≥ Σ
i
c(G
i
), and in [1] it is shown that in fact c(G) can be larger than any fixed power of the above sum.
We extend the ideas of [1] and show that for every F, a family of subsets of [t], it is possible to assign a channel C
i
to each sender i ∈ [t], such that the capacity of a group of senders X ⊂ [t] is high iff X contains some F ∈ F. This corresponds to a case where only privileged subsets of senders are allowed to transmit in a high rate. For instance,
as an analogue to secret sharing, it is possible to ensure that whenever at least k senders combine their channels, they obtain a high capacity, however every group of k − 1 senders has a low capacity (and yet is not totally denied of service). In the process, we obtain an explicit Ramsey construction
of an edge-coloring of the complete graph on n vertices by t colors, where every induced subgraph on exp vertices contains all t colors.
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. 相似文献