Search

The probabilistic version of a classical problem of extremal combinatorics is considered. The stability theorem which says that the independence number of a random subgraph of the graph remains asymptotically constant when edges are randomly removed is generalized to the case of nonconstant parameters. [ABSTRACT FROM AUTHOR]

A particular class of estimates related to the Nelson–Erdős–Hadwiger problem is studied. For two types of spaces, Euclidean and spaces with metric ℓ1, certain series of distance graphs of small dimensions are considered. Independence numbers of such graphs are estimated by using the linear-algebraic method and combinatorial observations. This makes it possible to obtain certain lower bounds for the chromatic numbers of the spaces mentioned above and, for each case, specify a series of graphs leading to the strongest results. [ABSTRACT FROM AUTHOR]

For a graph H, let $$\alpha (H)$$ and $$\alpha ^{\prime }(H)$$ denote the independence number and the matching number, respectively. Let $$k\ge 2$$ and $$r>0$$ be given integers. We prove that if H is a k-connected claw-free graph with $$\alpha (H)\le r$$ , then either H is Hamiltonian or the Ryjá c̆ ek's closure $$cl(H)=L(G)$$ where G can be contracted to a k-edge-connected $$K_3$$ -free graph $$G_0^{\prime }$$ with $$\alpha ^{\prime }(G_0^{\prime })\le r$$ and $$|V(G_0^{\prime })|\le \max \{3r-5, 2r+1\}$$ if $$k\ge 3$$ or $$|V(G_0^{\prime })|\le \max \{4r-5, 2r+1\}$$ if $$k=2$$ and $$G_0^{\prime }$$ does not have a dominating closed trail containing all the vertices that are obtained by contracting nontrivial subgraphs. As corollaries, we prove the following: Case (a) was first proved by Xu et al. [19]. Case (b) is an improvement of a result proved by Flandrin and Li [12]. For a given integer $$r>0$$ , the number of graphs of order at most $$\max \{4r-5, 2r+1\}$$ is fixed. The main result implies that improvements to case (a) or (b) by increasing the value of r and by enlarging the collection of exceptional graphs can be obtained with the help of a computer. Similar results involved degree or neighborhood conditions are also discussed. [ABSTRACT FROM AUTHOR]

Chvátal and Erdős proved a well-known result that the graph $$G$$ with connectivity $$\kappa (G)$$ not less than its independence number $$\alpha (G)$$ [ $$\alpha (G)+1$$ , $$\alpha (G)-1$$ , respectively] is Hamiltonian (traceable, Hamiltonian-connected, respectively). In this paper, we strengthen the Chvátal-Erdős theorem to the following: Let $$G$$ be a simple 2-connected graph of order large enough such that $$\alpha (G)\le \kappa (G)+1$$ [ $$\alpha (G)\le \kappa (G)+2$$ , $$\alpha (G)\le \kappa (G),$$ respectively] and such that the number of maximum independent sets of cardinality $$\kappa (G)+1$$ [ $$\kappa (G)+2$$ , $$\kappa (G)$$ , respectively] is at most $$n-2\kappa (G)$$ [ $$n-2\kappa (G)-1$$ , $$n-2\kappa (G)+1$$ , respectively]. Then $$G$$ is either Hamiltonian (traceable, Hamiltonian-connected, respectively) or a subgraph of $$K_{k}+((kK_1)\cup K_{n-2k})$$ [ $$K_{k}+((k+1)K_1\cup K_{n-2k-1})$$ , $$K_{k}+((k-1)K_1\cup K_{n-2k+1})$$ , respectively]. [ABSTRACT FROM AUTHOR]

In this paper, we deal with a probabilistic version of a classical problem in extremal combinatorics. An extension to the case of nonconstant parameters and to the case of different probabilities of edges is established for a stability theorem asserting that the independence number of a random subgraph of a graph does not change asymptotically, provided that the initial edges are deleted independently. [ABSTRACT FROM AUTHOR]

Brown, Nowakowski and Rall defined the ultimate categorical independence ratio of a graph G as A(G)=limk → ∞ i(G × k), where i(G)= α (G)|V(G)| denotes the independence ratio of a graph G, and G × k is the kth categorical power of G. Let a(G)=max{|U||U|+|NG(U)|:U is an independent set of G}, where NG(U) is the neighborhood of U in G. In this paper we answer a question of Alon and Lubetzky, namely we prove that A(G)=a(G) if a(G) ≼ 12, and A(G)=1 otherwise. We also discuss some other open problems related to A(G) which are immediately settled by this result. [ABSTRACT FROM AUTHOR]

We obtain new lower bounds for the independence number of Kr-free graphs and linear k-uniform hypergraphs in terms of the degree sequence. This answers some old questions raised by Caro and Tuza [J. Graph Theory, 15 (1991), pp. 99-107]. Our proof technique is an extension of a method of Caro [New Results on the Independence Number, Technical report, Tel Aviv University, 1979] and Wei [A Lower Bound on the Stability Number of a Simple Graph, TM 81-11217-9, Bell Laboratories, Berkley Heights, NJ, 1981], and we also give a new short proof of the main result of Caro and Tuza using this approach. As byproducts, we also obtain some nontrivial identities involving binomial coefficients, which may be of independent interest. [ABSTRACT FROM AUTHOR]

Abstract: The direct product of graphs G and H is defined by and In this paper, we will prove that holds for all vertex-transitive graphs G and H, which provides an affirmative answer to a problem posed by Tardif (1998) . Furthermore, the structure of all maximum independent sets of is determined. [Copyright &y& Elsevier]

The Hadwiger number h(G) of a graph G is the maximum size of a complete minor of G. Hadwiger's Conjecture states that h(G) =X(G). Since X(G)α(G) ≥|V (G)|, Hadwiger's Conjecture implies that α(G)h(G) ≥ |V (G)|. We show that (2α(G)-[log τ(τα(G)/2)])h(G) ≥ |V (G)| where τ ∼ 6.83. For graphs with α(G) = 14, this improves on a recent result of Kawarabayashi and Song who showed (2α(G) - 2) h(G) ≥ |V (G)| when α(G) = 3. [ABSTRACT FROM AUTHOR]

Abstract: A weakening of Hadwiger’s conjecture states that every -vertex graph with independence number has a clique minor of size at least . Extending ideas of Fox (2010) , we prove that such a graph has a clique minor with at least vertices where . [Copyright &y& Elsevier]

In this paper, we give a sufficient condition for a graph to have a degree bounded spanning tree. Let n ≥ 1, k ≥ 3, c ≥ 0 and G be an n-connected graph. Suppose that for every independent set $${S \subseteq V(G)}$$ of cardinality n( k−1) + c + 2, there exists a vertex set $${X \subseteq S}$$ of cardinality k such that the degree sum of vertices in X is at least | V( G)| − c −1. Then G has a spanning tree T with maximum degree at most $${k+\lceil c/n\rceil}$$ and $${\sum_{v\in V(T)}\max\{d_T(v)-k,0\}\leq c}$$ . [ABSTRACT FROM AUTHOR]

Abstract: The complexity status of the Maximum Independent Set Problem (MIS) for the family of -free graphs is unknown. Although for many subclasses of -free graphs MIS can be solved in polynomial time, only exponential time MIS-algorithms for general graphs are known so far. In this note we present the first algorithm to solve MIS for -free graphs in subexponential time. [Copyright &y& Elsevier]

Abstract: The Conjecture of Hadwiger implies that the Hadwiger number times the independence number of a graph is at least the number of vertices of the graph. In 1982 Duchet and Meyniel [P. Duchet, H. Meyniel, On Hadwiger’s number and the stability number, Ann. of Discrete Math. 13 (1982) 71–74] proved a weak version of the inequality, replacing the independence number by , that is, In 2005 Kawarabayashi, Plummer and the second author [K. Kawarabayashi, M. Plummer, B. Toft, Improvements of the theorem of Duchet and Meyniel on Hadwiger’s Conjecture, J. Combinatorial Theory B 95 (2005) 152–167] published an improvement of the theorem, replacing by when is at least 3. Since then a further improvement by Kawarabayashi and Song has been obtained, replacing by when is at least 3. In this paper a basic elementary extension of the Theorem of Duchet and Meyniel is presented. This may be of help to avoid dealing with basic cases when looking for more substantial improvements. The main unsolved problem (due to Seymour) is to improve, even just slightly, the theorem of Duchet and Meyniel in the case when the independence number is equal to 2. The case of Hadwiger’s Conjecture was first pointed out by Mader as an interesting special case. [Copyright &y& Elsevier]

Fouquet and Jolivet conjectured that a k-connected graph of order n and independence number α ≥ k has a cycle of length at least $$\frac {k(n+\alpha -k)}{\alpha}$$ [Fouquet and Jolivet, Problèmes combinatoires et théorie des graphes Orsay (1976), Problems, page 438]. Here we prove this conjecture for k=3. [ABSTRACT FROM AUTHOR]

Abstract: Let and denote the independence number and chromatic number of a graph G, respectively. Let be the direct product graph of graphs G and H. We show that if G and H are circular graphs, Kneser graphs, or powers of cycles, then and . [Copyright &y& Elsevier]

Abstract: A maximum independent set of vertices in a graph is a set of pairwise nonadjacent vertices of largest cardinality . Plummer [Some covering concepts in graphs, J. Combin. Theory 8 (1970) 91–98] defined a graph to be well-covered, if every independent set is contained in a maximum independent set of G. Every well-covered graph G without isolated vertices has a perfect -factor , i.e. a spanning subgraph such that each component is 1-regular or 2-regular. Here, we characterize all well-covered graphs G satisfying for some perfect -factor . This class contains all well-covered graphs G without isolated vertices of order n with , and in particular all very well-covered graphs. [Copyright &y& Elsevier]

Abstract: Since , Hadwiger''s conjecture implies that any graph G has the complete graph as a minor, where is the number of vertices of G and is the maximum number of independent vertices in G. Duchet and Meyniel [Ann. Discrete Math. 13 (1982) 71–74] proved that any G has as a minor. For G has as a minor. Paul Seymour asked if it is possible to obtain a larger constant than for this case. To our knowledge this has not yet been achieved. Our main goal here is to show that the constant of Duchet and Meyniel can be improved to a larger constant, depending on , for all . Our method does not work for and we only present some observations on this case. [Copyright &y& Elsevier]

Let H be a hypergraph with N vertices and average degree d. Suppose that the neighborhoods of H are sparse, then its independence number is at least cN(logd /d), where c>0 is a constant. In particular, let integers r≥3 and n≥1 be fixed, and let H be r-uniform, triangle-free and linear, then its independence number is at least cNlognd/d for all sufficiently large d. [Copyright &y& Elsevier]

Abstract: In 1968, Vizing conjectured that, if G is a -critical graph with n vertices, then , where is the independence number of G. In this note, we verify this conjecture for . [Copyright &y& Elsevier]

The article cites a study which investigates the lower bounds for the independence numbers of distance graphs along with vertices. The study examines the so-called multiparameter construction, which is probably optimal for searching the correct choice of the parameters. It also highlights the Borsuk problem which is designed to find the minimal number.