Odd Subgraphs And Matchings

Kano, M; Katona, GY [Katona, Gyula Y. (gráfelmélet), szerző] Számítástudományi és Információelméleti Tanszék (BME / VIK)

Angol nyelvű Tudományos Szakcikk (Folyóiratcikk)
Megjelent: DISCRETE MATHEMATICS 0012-365X 1872-681X 250 (1-3) pp. 265-272 2002
  • SJR Scopus - Discrete Mathematics and Combinatorics: Q2
Szakterületek:
    Let G be a graph and f : V(G) --> {1, 3, 5,...}. Then a subgraph H of G is called a (1, f)-odd subgraph if deg(H)(x) is an element of {1, 3,..., f(x)} for all x is an element of V(H). If f(x) = 1 for all x is an element of V(G), then a (1, f)-odd subgraph is nothing but a matching. A (1, f)-odd subgraph H of G is said to be maximum if G has no (1, f)-odd subgraph K such that K > H. We show that (1, f)-odd subgraphs have some properties similar to those of matchings, in particular, we give a formula for the order of a maximum (1, f)-odd subgraph, which is similar to that for the order of a maximum matching. (C) 2002 Elsevier Science B.V. All rights reserved.
    Hivatkozás stílusok: IEEEACMAPAChicagoHarvardCSLMásolásNyomtatás
    2022-01-20 02:05