Displaying similar documents to “A note on the paper by K. Feng 'Non-congruent numbers, odd graphs and the Birch-Swinnerton-Dyer conjecture' (Acta Arith. 75 (1996), 71-83)”

Complete minors, independent sets, and chordal graphs

József Balogh, John Lenz, Hehui Wu (2011)

Discussiones Mathematicae Graph Theory

Similarity:

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) ≥ χ(G). Since χ(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.

On a special case of Hadwiger's conjecture

Michael D. Plummer, Michael Stiebitz, Bjarne Toft (2003)

Discussiones Mathematicae Graph Theory

Similarity:

Hadwiger's Conjecture seems difficult to attack, even in the very special case of graphs G of independence number α(G) = 2. We present some results in this special case.

On Vizing's conjecture

Bostjan Bresar (2001)

Discussiones Mathematicae Graph Theory

Similarity:

A dominating set D for a graph G is a subset of V(G) such that any vertex in V(G)-D has a neighbor in D, and a domination number γ(G) is the size of a minimum dominating set for G. For the Cartesian product G ⃞ H Vizing's conjecture [10] states that γ(G ⃞ H) ≥ γ(G)γ(H) for every pair of graphs G,H. In this paper we introduce a new concept which extends the ordinary domination of graphs, and prove that the conjecture holds when γ(G) = γ(H) = 3.

Vizing's conjecture and the one-half argument

Bert Hartnell, Douglas F. Rall (1995)

Discussiones Mathematicae Graph Theory

Similarity:

The domination number of a graph G is the smallest order, γ(G), of a dominating set for G. A conjecture of V. G. Vizing [5] states that for every pair of graphs G and H, γ(G☐H) ≥ γ(G)γ(H), where G☐H denotes the Cartesian product of G and H. We show that if the vertex set of G can be partitioned in a certain way then the above inequality holds for every graph H. The class of graphs G which have this type of partitioning includes those whose 2-packing number is no smaller than γ(G)-1 as...

An update on a few permanent conjectures

Fuzhen Zhang (2016)

Special Matrices

Similarity:

We review and update on a few conjectures concerning matrix permanent that are easily stated, understood, and accessible to general math audience. They are: Soules permanent-on-top conjecture†, Lieb permanent dominance conjecture, Bapat and Sunder conjecture† on Hadamard product and diagonal entries, Chollet conjecture on Hadamard product, Marcus conjecture on permanent of permanents, and several other conjectures. Some of these conjectures are recently settled; some are still open.We...