A set S of vertices of a graph is odd independent if it is independent and every vertex outside S has either zero or an odd number of neighbors in S. The largest size of such a set is the odd independence number alpha_od. Caro, Petrusevski, Skrekovski and Tuza [2] conjectured that alpha_od = 1 for every finite Queen graph. They also asked whether the infinite Queen graph has alpha_od = 1 or alpha_od = infinity. We prove that alpha_od = 1 in both cases. In particular, in the case of an infinite board we prove that alpha_od = 1 holds on the quarter plane and on the whole plane.
A graph is
perfect
if, for every induced subgraph, the chromatic number equals the size of its largest clique. In 1972, Lovász established a fundamental characterization of perfect graphs, showing that a graph is perfect if and only if, for every induced subgraph, the product of the size of the largest independen...
The representation number of a graph is the smallest integer k such that the graph can be represented by a word in which each vertex appears exactly k times, and two distinct vertices x and y alternate in the word if and only if they are adjacent in the graph. We extend known results on the representation number for va...
S. Kitaev, A. Pyatkin· Acta Informatica· 0 citations
The strong Ramsey number R¯(F,H) of two graphs F and H without isolated vertices is the minimum positive integer n such that every red-blue (edge) coloring of Kn results in two edge-disjoint monochromatic subgraphs, one isomorphic to F and the other isomorphic to H. These numbers have been determined for all such pairs...
K\"{u}hn, Sauermann, Steiner and Wigderson recently disproved the Odd Hadwiger Conjecture, even for graphs with independence number 2. For this class of graphs the conjecture is known to be equivalent to the following: every $n$-vertex graph $G$ with independence number 2 contains $K_{\lceil \frac n2 \rceil}$ as an odd...
Antonia Bermúdez, Bruno L. Netto, Daniel A. Quiroz· 0 citations
For a graph $G$, let $i_k(G)$ denote the number of independent sets of cardinality $k$, and let \[ I(G,z)=\sum_{k\ge0} i_k(G)z^k \] be its independence polynomial. Following Brown and Cameron \cite{BrownCameron2018}, a graph is called stable if all zeros of its independence polynomial lie in the closed left half-plane....
For planar graphs, it is known that their treewidth is bounded by $O(\sqrt{n})$, where $n$ is the number of vertices of the graph. A related invariant to treewidth, is the scramble number of graphs. Recently, Connor et. al proved that planar graphs of bounded maximal degree have scramble number bounded by $O(\sqrt{n})$...
Doel Rivera Laboy· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
