Transactions on Combinatorics
Volume:8 Issue: 3, Sep 2019

‎‎We derive a new sharp lower bound on the $k$-conversion number of graphs of maximum degree $k+1$‎. ‎This generalizes a result of W.~Staton [Induced forests in cubic graphs‎, ‎Discrete Math.‎,49 (‎1984) ‎175--178‎]‎, ‎which established a lower bound on the $k$-conversion number of $(k+1)$-regular graphs‎.

A fall coloring of a graph $G$ is a proper‎ coloring of $G$ with $k$ colors such that each vertex sees ‎all $k$‎ colors on its closed neighborhood‎. ‎In this paper‎, ‎we characterize ‎‎‎all fall colorings of Kneser graphs of type $KG(n,2)$‎.

A linear $ [n,k]_q $ code $ C $ is said to be a full weight spectrum (FWS) code if there exist codewords of each weight less than or equal to $ n $. In this brief communication we determine necessary and sufficient conditions for the existence of linear $ [n,k]_q $ full weight spectrum (FWS) codes. Central to our approach is the geometric view of linear codes, whereby columns of a generator matrix correspond to points in $ PG(k-1,q) $.

In this paper we prove a generalized version of Hall's theorem in graphs‎, ‎for hypergraphs‎. ‎More precisely‎, ‎let $mathcal{H}$ be a $k$-uniform $k$-partite hypergraph with some ordering on parts as $V_{1}‎, ‎V_{2}‎,‎ldots‎,‎V_{k}$ such that the subhypergraph generated on $bigcup_{i=1}^{k-1}V_{i}$ has a unique perfect matching‎. ‎In this case‎, ‎we give a necessary and sufficient condition for having a matching of size $t=|V_{1}|$ in $mathcal{H}$‎. ‎Some relevant results and counterexamples are given as well‎.

‎Let $G$ be a simple graph‎. ‎The graph $G$ is called a quasi unicyclic graph if there exists a vertex $x in V(G)$ such that $G-x$ is a connected graph with a unique cycle‎. ‎Moreover‎, ‎the first and the second Zagreb indices of $G$ denoted by $M_1(G)$ and $M_2(G)$‎, ‎are the sum of $deg^2(u)$ overall vertices $u$ in $G$ and the sum of $deg(u)deg(v)$ of all edges $uv$ of $G$‎, ‎respectively‎. ‎The first and the second Zagreb indices are defined relative to the degree of vertices‎. ‎In this paper‎, ‎sharp upper and lower bounds for the first and the second Zagreb indices of quasi unicyclic graphs are given‎.