Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Opuscula Mathematica

Powiadomienia systemowe

Sesja wygasła!

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

On strongly spanning k-edge-colorable subgraphs

Mkrtchyan V. V., Vardanyan G. N.

Opuscula Mathematica

2017

Vol. 37, no. 3

447--456

A subgraph H of a multigraph G is called strongly spanning, if any vertex of G is not isolated in H. H 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 for which a multigraph G has a maximum k-edge-colorable subgraph that is strongly spanning. 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 multigraphs G that satisfy sp(G) = Δ (G). Finally, we prove some bounds for sp(G) that involve well-known graph-theoretic parameters.

The hardness of the independence and matching clutter of a graph

Hambardzumyan S., Mkrtchyan V. V., Musoyan V. L., Sargsyan H.

Opuscula Mathematica

2016

Vol. 36, no. 3

375--397

A clutter (or antichain or 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 vertices of L, and the elements of E are called edges of L. A subset se of an edge e of a clutter is called recognizing for e, if se is not a subset of another edge. The 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.