Search

Let $G$ be a graph of order $n$. A path decomposition $\mathcal{P}$ of $G$ is a collection of edge-disjoint paths that covers all the edges of $G$. Let $p(G)$ denote the minimum number of paths needed in a path decomposition of $G$. Gallai conjectured that if $G$ is connected, then $p(G)\leq \lceil\frac{n}{2}\rceil$. In this paper, we prove that Gallai's path decomposition conjecture holds for the cartesian product $G\Box H$, where $H$ is any graph and $G$ is a unicyclic graph or a bicyclic graph., Comment: 26 pages, 2 figures. arXiv admin note: text overlap with arXiv:2310.11189

Let $G$ be a graph of order $n$. A path decomposition $\mathcal{P}$ of $G$ is a collection of edge-disjoint paths that covers all the edges of $G$. Let $p(G)$ denote the minimum number of paths needed in a path decomposition of $G$. Gallai conjectured that if $G$ is connected, then $p(G)\leq \lceil\frac{n}{2}\rceil$. Let $n_o(G)$ to denote the number of vertices with odd degree in $G$. Lov\'{a}sz proved that if $G$ is a connected graph with all vertices having degree odd, i.e. $n_o(G)=n$, then $p(G)=\frac n 2$. In this paper, we prove that if $G$ is a connected graph of order $m\geq 2$ with $p(G)=\frac{n_o(G)}{2}$ and $H$ is a connected graph of order $n$, then $p(G\Box H)\leq\frac{mn}{2}$. Furthermore, we prove that $p(G)=\frac{n_o(G)}{2}$, if one of the following is hold: (\romannumeral1) $G$ is a tree; (\romannumeral2) $G=P_n\Box T$, where $n\geq 4$ and $T$ is a tree; (\romannumeral3) $G=P_n\Box H$, where $H$ is an even graph., Comment: 12 pages, 4 figures

Let $f_{o}(G)$ be the maximum order of an odd induced subgraph of $G$. In 1992, Scott proposed a conjecture that $f_{o}(G)\geq \frac {n} {2\chi(G)}$ for a graph $G$ of order $n$ without isolated vertices, where $\chi(G)$ is the chromatic number of $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 $f_{o}(G)\geq 2\lfloor\frac {n} {4}\rfloor$ for a connected graph $G$ of order $n$. Scott's conjecture is open for a graph with chromatic number at least 3., Comment: 18 pages, 6 figure

Very recently, the first geometric-arithmetic index $GA$ and arithmetic-geometric index $AG$ were introduced in mathematical chemistry. In the present paper, we first obtain some lower and upper bounds on $AG$ and characterize the extremal graphs. We also establish various relations between $AG$ and other topological indices, such as the first geometric-arithmetic index $GA$, atom-bond-connectivity index $ABC$, symmetric division deg index $SDD$, chromatic number $\chi$ and so on. Finally, we present some sufficient conditions of $GA(G)>GA(G-e)$ or $AG(G)>AG(G-e)$ for an edge $e$ of a graph $G$. In particular, for the first geometric-arithmetic index, we also give a refinement of Bollob\'{a}s-Erd\H{o}s-type theorem obtained in [3]., Comment: 24 pages, 4 figures, 32 conferences

Bollob\'as and Nikiforov [J. Combin. Theory, Ser. B. 97 (2007) 859--865] conjectured the following. If $G$ is a $K_{r+1}$-free graph on at least $r+1$ vertices and $m$ edges, then $\lambda^2_1(G)+\lambda^2_2(G)\leq \frac{r-1}{r}\cdot2m$, where $\lambda_1(G)$ and $\lambda_2(G)$ are the largest and the second largest eigenvalues of the adjacency matrix $A(G)$, respectively. In this paper, we confirm the conjecture in the case $r=2$, by using tools from doubly stochastic matrix theory, and also characterize all families of extremal graphs. Motivated by classic theorems due to Erd\H{o}s and Nosal respectively, we prove that every non-bipartite graph $G$ of order $n$ and size $m$ contains a triangle, if one of the following is true: (1) $\lambda_1(G)\geq\sqrt{m-1}$ and $G\neq C_5\cup (n-5)K_1$; and (2) $\lambda_1(G)\geq \lambda_1(S(K_{\lfloor\frac{n-1}{2}\rfloor,\lceil\frac{n-1}{2}\rceil}))$ and $G\neq S(K_{\lfloor\frac{n-1}{2}\rfloor,\lceil\frac{n-1}{2}\rceil})$, where $S(K_{\lfloor\frac{n-1}{2}\rfloor,\lceil\frac{n-1}{2}\rceil})$ is obtained from $K_{\lfloor\frac{n-1}{2}\rfloor,\lceil\frac{n-1}{2}\rceil}$ by subdividing an edge. Both conditions are best possible. We conclude this paper with some open problems., Comment: 15 pages, accepted version for publication in Combinatorics, Probability and Computing

The feedback vertex number $\tau(G)$ of a graph $G$ is the minimum number of vertices that can be deleted from $G$ such that the resultant graph does not contain a cycle. We show that $\tau(S_p^n)=p^{n-1}(p-2)$ for the Sierpi\'{n}ski graph $S_p^n$ with $p\geq 2$ and $n\geq 1$. The generalized Sierpi\'{n}ski triangle graph $\hat{S_p^n}$ is obtained by contracting all non-clique edges from the Sierpi\'{n}ski graph $S_p^{n+1}$. We prove that $\tau(\hat{S}_3^n)=\frac {3^n+1} 2=\frac{|V(\hat{S}_3^n)|} 3$, and give an upper bound for $\tau(\hat{S}_p^n)$ for the case when $p\geq 4$., Comment: 20 pages; 8 figures

A path in a vertex-colored graph is called {\it conflict-free} if there is a color used on exactly one of its vertices. A vertex-colored graph is said to be {\it conflict-free vertex-connected} if any two vertices of the graph are connected by a conflict-free path. The {\it conflict-free vertex-connection number}, denoted by $vcfc(G)$, is defined as the smallest number of colors required to make $G$ conflict-free vertex-connected. Li et al. conjectured that for a connected graph $G$ of order $n$, $vcfc(G)\leq vcfc(P_n)$. We confirm that the conjecture is true and pose a a relevant conjecture concerning the conflict-free connection number introduced by Czap et al.., Comment: 5 pages

Let $G$ be a simple graph with $n\geq4$ vertices and $d(x)+d(y)\geq n+k$ for each edge $xy\in E(G)$. In this work we prove that $G$ either contains a spanning closed trail containing any given edge set $X$ if $|X|\leq k$, or $G$ is a well characterized graph. As a corollary, we show that line graphs of such graphs are $k$-hamiltonian., Comment: 7 pages

Let $G=(V, E)$ be a graph. A set $S\subseteq V(G)$ is a {\it dominating set} of $G$ if every vertex in $V\setminus S$ is adjacent to a vertex of $S$. The {\it domination number} of $G$, denoted by $\gamma(G)$, is the cardinality of a minimum dominating set of $G$. Furthermore, a dominating set $S$ is an {\it independent transversal dominating set} of $G$ if it intersects every maximum independent set of $G$. The {\it independent transversal domination number} of $G$, denoted by $\gamma_{it}(G)$, is the cardinality of a minimum independent transversal dominating set of $G$. In 2012, Hamid initiated the study of the independent transversal domination of graphs, and posed the following two conjectures: Conjecture 1. If $G$ is a non-complete connected graph on $n$ vertices, then $\gamma_{it}(G)\leq\lceil\frac{n}{2}\rceil$. Conjecture 2. If G is a connected bipartite graph, then $\gamma_{it}(G)$ is either $\gamma(G)$ or $\gamma(G)+1$. We show that Conjecture 1 is not true in general. Very recently, Conjecture 2 is partially verified to be true by Ahangar, Samodivkin, Yero. Here, we prove the full statement of Conjecture 2. In addition, we give a correct version of a theorem of Hamid. Finally, we answer a problem posed by Mart\'{i}nez, Almira, and Yero on the independent transversal total domination of a graph., Comment: 9 pages