Graph Theory
This book is based on Graph Theory courses taught by P.A. Petrosyan, V.V. Mkrtchyan and R.R. Kamalian at Yerevan State University.
Source author record
Vahan V. Mkrtchyan
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
ResearcherUnclaimed source record
Catalog footprint
Research overview
10works
2topics
4close collaborators
Published work
10 publications
preprint2015arXiv
On strongly spanning k-edge-colorable subgraphs
A subgraph H of a multigraph G is called strongly spanning, if any vertex of G is not isolated in H, while it is called maximum k-edge-colorable, if H is proper k-edge-colorable and has the largest size. We introduce a graph-parameter sp(G), that coincides with the smallest k that a graph G has a strongly spanning maximum k-edge-colorable subgraph. Our first result offers some alternative definitions of sp(G). Next, we show that Δ(G) is an upper bound for sp(G), and then we characterize the class of graphs G that satisfy sp(G)=Δ(G). Finally, we prove some bounds for sp(G) that involve well-known graph-theoretic parameters.
Open access
preprint2015arXiv
The hardness of the independence and matching clutter of a graph
A {\it clutter} (or {\it antichain} or {\it Sperner family}) L is a pair (V,E), where V is a finite set and E is a family of subsets of V none of which is a subset of another. Usually, the elements of V are called {\it vertices} of L, and the elements of E are called {\it edges} of L. A subset se of an edge e of a clutter is called {\it recognizing} for e, if se is not a subset of another edge. The {\it hardness} of an edge e of a clutter is the ratio of the size of e’s smallest recognizing subset to the size of e. The hardness of a clutter is the maximum hardness of its edges. We study the hardness of clutters arising from independent sets and matchings of graphs.
Open access
preprint2012arXiv
A remark on Petersen coloring conjecture of Jaeger
If G and H are two cubic graphs, then we write H≺G, if G admits a proper edge-coloring f with edges of H, such that for each vertex x of G, there is a vertex y of H with f(∂G(x))=∂H(y). Let P and S be the Petersen graph and the Sylvester graph, respectively. In this paper, we introduce the Sylvester coloring conjecture. Moreover, we show that if G is a connected bridgeless cubic graph with G≺P, then G=P. Finally, if G is a connected cubic graph with G≺S, then G=S.
Open access
preprint2012arXiv
Equitable Colorings of Corona Multiproducts of Graphs
A graph is equitably k-colorable if its vertices can be partitioned into k independent sets in such a way that the number of vertices in any two sets differ by at most one. The smallest k for which such a coloring exists is known as the equitable chromatic number of G and denoted χ=(G). It is known that this problem is NP-hard in general case and remains so for corona graphs. In "Equitable colorings of Cartesian products of graphs" (2012) Lin and Chang studied equitable coloring of Cartesian products of graphs. In this paper we consider the same model of coloring in the case of corona products of graphs. In particular, we obtain some results regarding the equitable chromatic number for l-corona product G∘lH, where G is an equitably 3- or 4-colorable graph and H is an r-partite graph, a path, a cycle or a complete graph. Our proofs are constructive in that they lead to polynomial algorithms for equitable coloring of such graph products provided that there is given an equitable coloring of G. Moreover, we confirm Equitable Coloring Conjecture for corona products of such graphs. This paper extends our results from \cite{hf}.
Open access
preprint2012arXiv
On disjoint matchings in cubic graphs: maximum 2- and 3-edge-colorable subgraphs
We show that any 2−factor of a cubic graph can be extended to a maximum 3−edge-colorable subgraph. We also show that the sum of sizes of maximum 2− and 3−edge-colorable subgraphs of a cubic graph is at least twice of its number of vertices. Finally, for a cubic graph G, consider the pairs of edge-disjoint matchings whose union consists of as many edges as possible. Let H be the largest matching among such pairs. Let M be a maximum matching of G. We show that 9/8 is a tight upper bound for ∣M∣/∣H∣.
Open access
preprint2011arXiv
A note on triangle-free graphs
We show that if G is a simple triangle-free graph with n≥3 vertices, without a perfect matching, and having a minimum degree at least 2n−1, then G is isomorphic either to C5 or to K2n−1,2n+1.
Open access
preprint2011arXiv
Maximum Δ-edge-colorable subgraphs of class II graphs
A graph G is class II, if its chromatic index is at least Δ+1. Let H be a maximum Δ-edge-colorable subgraph of G. The paper proves best possible lower bounds for ∣E(G)∣∣E(H)∣, and structural properties of maximum Δ-edge-colorable subgraphs. It is shown that every set of vertex-disjoint cycles of a class II graph with Δ≥3 can be extended to a maximum Δ-edge-colorable subgraph. Simple graphs have a maximum Δ-edge-colorable subgraph such that the complement is a matching. Furthermore, a maximum Δ-edge-colorable subgraph of a simple graph is always class I.
Open access
preprint2011arXiv
On upper bounds for parameters related to construction of special maximum matchings
For a graph G let L(G) and l(G) denote the size of the largest and smallest maximum matching of a graph obtained from G by removing a maximum matching of G. We show that L(G)≤2l(G), and L(G)≤(3/2)l(G) provided that G contains a perfect matching. We also characterize the class of graphs for which L(G)=2l(G). Our characterization implies the existence of a polynomial algorithm for testing the property L(G)=2l(G). Finally we show that it is NP-complete to test whether a graph G containing a perfect matching satisfies L(G)=(3/2)l(G).
Open access
preprint2010arXiv
On disjoint matchings in cubic graphs
For i=2,3 and a cubic graph G let νi(G) denote the maximum number of edges that can be covered by i matchings. We show that ν2(G)≥4/5∣V(G)∣ and ν3(G)≥7/6∣V(G)∣. Moreover, it turns out that ν2(G)≤4∣V(G)∣+2ν3(G).
Open access
Research graph
See the researcher in context
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.