فهرست مطالب
Transactions on Combinatorics
Volume:8 Issue: 3, Sep 2019
- تاریخ انتشار: 1398/06/10
- تعداد عناوین: 5
-
-
Pages 1-12We 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.Keywords: irreversible k-threshold conversion process, network diffusion process, conversion number, conversion set
-
Pages 13-15A 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)$.Keywords: Kneser graph, fall coloring, b-coloring
-
Pages 15-22A 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) $.Keywords: weight spectrum, linear code, Hamming weight, FWS, MWS
-
Pages 23-28
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.
Keywords: $k$-uniform $k$-partite hypergraph, matching, perfect matching, vertex cover, Hall', s theorem -
Pages 29-39Let $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.Keywords: First Zagreb index, Second Zagreb index, Quasi Unicyclic graphs