Institutul de Matematică şi Informatică "Vladimir Andrunachievici"
Universitatea de Stat din MoldovaRO EN
Graphs, Disjoint Matchings and Some Inequalities
Authors: Lianna Hambardzumyan, Vahan Mkrtchyan
Keywords: Bipartite graph, Tree, Unicyclic graph, Edge-coloring, Parsimonious edge-coloring
– 0.13 Mb
Keywords: Bipartite graph, Tree, Unicyclic graph, Edge-coloring, Parsimonious edge-coloring
Abstract
A graph $G$ is $k$-edge-colorable if the edges of $G$ can be assigned a color from $\{1,...,k\}$ so that adjacent edges of $G$ receive different colors. A maximum $k$-edge-colorable subgraph of $G$ is a $k$-edge-colorable subgraph of $G$ containing maximum number of edges. For $k \geq 1$ and a graph $G$, let $\nu_k(G)$ denote the number of edges in a maximum $k$-edge-colorable subgraph of $G$. In 2010 Mkrtchyan, Petrosyan and Vardanyan proved that if $G$ is a cubic graph, then $\nu_2(G) \leq \frac{|V(G)| + 2\cdot \nu_3(G)}{4}$ ~\cite{samvel:2010}. For cubic graphs containing a perfect matching, in particular, for bridgeless cubic graphs, this inequality can be stated as $\nu_2(G) \leq \frac{\nu_1(G) + \nu_3(G)}{2}$. One may wonder whether there are other well-known graph classes, where a similar result can be obtained. In this work, we prove lower bounds for $\nu_k(G)$ in terms of $\frac{\nu_{k-1}(G)+\nu_{k+1}(G)}{2}$ for $k\geq 2$ and graphs $G$ containing at most $1$ cycle. We also present the corresponding conjectures for nearly bipartite graphs. }Lianna Hambardzumyan
Department of Informatics and Applied Mathematics,
Yerevan State University, Yerevan, 0025, Armenia
E-mail:
Vahan Mkrtchyan
Gran Sasso Science Institute, School
of Advanced Studies, L’Aquila, Italy
E-mail:
Department of Informatics and Applied Mathematics,
Yerevan State University, Yerevan, 0025, Armenia
E-mail:
Vahan Mkrtchyan
Gran Sasso Science Institute, School
of Advanced Studies, L’Aquila, Italy
E-mail:
DOI
https://doi.org/10.56415/basm.y2023.i3.p26Fulltext
– 0.13 Mb
Contents
- On some applications of relative (p,q)-th order for rating the growths of composite entire functions
- Graphs, Disjoint Matchings and Some Inequalities
- Existence of solutions to multi-point boundary value problem of fractional order on the half-line
- Some subsets in bitopological spaces and bioperations continuity associated
- Approximation of fixed points in convex G-metric spaces
- Finite algebras in the design of multivariate cryptography algorithms
- A note on the Kirichenko--Uskorev structure
- Exact solutions to differential equations with different arguments
- On the order of recursive differentiability of finite binary quasigroups
