Search

Let fo(G) ${f}_{o}(G)$ be the maximum order of an odd induced subgraph of G $G$. In 1992, Scott proposed a conjecture that fo(G)≥nχ(G) ${f}_{o}(G)\ge \frac{n}{\chi (G)}$ for a graph G $G$ of order n $n$ without isolated vertices, where χ(G) $\chi (G)$ is the chromatic number of G $G$. In this paper, we show that the conjecture is not true for bipartite graphs, but is true for all line graphs. In addition, we also disprove a conjecture of Berman, Wang, and Wargo in 1997, which states that fo(G)≥2n4 ${f}_{o}(G)\ge 2\unicode{x0230A}\frac{n}{4}\unicode{x0230B}$ for a connected graph G $G$ of order n $n$. Scott's conjecture is open for graphs with chromatic number at least 3. [ABSTRACT FROM AUTHOR]

In this paper, we study the Wiener index of the orientation of trees and theta‐graphs. An orientation of a tree is called no‐zig‐zag if there is no subpath in which edges change the orientation twice. Knor, Škrekovski, and Tepeh conjectured that every orientation of a tree T $T$ achieving the maximum Wiener index is no‐zig‐zag. We disprove this conjecture by constructing a counterexample. Knor, Škrekovski, and Tepeh conjectured that among all orientations of the theta‐graph Θa,b,c ${{\rm{\Theta }}}_{a,b,c}$ with a≥b≥c $a\ge b\ge c$ and b>1 $b\gt 1$, the maximum Wiener index is achieved by the one in which the union of the paths between u1 ${u}_{1}$ and u2 ${u}_{2}$ forms a directed cycle of length a+b+2 $a+b+2$, where u1 ${u}_{1}$ and u2 ${u}_{2}$ are the vertex of degree 3. We confirm the validity of the conjecture. [ABSTRACT FROM AUTHOR]