Displaying similar documents to “Degree powers in graphs with forbidden subgraphs.”

One-Three Join: A Graph Operation and Its Consequences

M.A. Shalu, S. Devi Yamini (2017)

Discussiones Mathematicae Graph Theory

Similarity:

In this paper, we introduce a graph operation, namely one-three join. We show that the graph G admits a one-three join if and only if either G is one of the basic graphs (bipartite, complement of bipartite, split graph) or G admits a constrained homogeneous set or a bipartite-join or a join. Next, we define ℳH as the class of all graphs generated from the induced subgraphs of an odd hole-free graph H that contains an odd anti-hole as an induced subgraph by using one-three join and co-join...

Pₘ-saturated bipartite graphs with minimum size

Aneta Dudek, A. Paweł Wojda (2004)

Discussiones Mathematicae Graph Theory

Similarity:

A graph G is said to be H-saturated if G is H-free i.e., (G has no subgraph isomorphic to H) and adding any new edge to G creates a copy of H in G. In 1986 L. Kászonyi and Zs. Tuza considered the following problem: for given m and n find the minimum size sat(n;Pₘ) of Pₘ-saturated graph of order n. They gave the number sat(n;Pₘ) for n big enough. We deal with similar problem for bipartite graphs.

α-Labelings of a Class of Generalized Petersen Graphs

Anna Benini, Anita Pasotti (2015)

Discussiones Mathematicae Graph Theory

Similarity:

An α-labeling of a bipartite graph Γ of size e is an injective function f : V (Γ) → {0, 1, 2, . . . , e} such that {|ƒ(x) − ƒ(y)| : [x, y] ∈ E(Γ)} = {1, 2, . . . , e} and with the property that its maximum value on one of the two bipartite sets does not reach its minimum on the other one. We prove that the generalized Petersen graph PSn,3 admits an α-labeling for any integer n ≥ 1 confirming that the conjecture posed by Vietri in [10] is true. In such a way we obtain an infinite class...

Bounds on the Signed 2-Independence Number in Graphs

Lutz Volkmann (2013)

Discussiones Mathematicae Graph Theory

Similarity:

Let G be a finite and simple graph with vertex set V (G), and let f V (G) → {−1, 1} be a two-valued function. If ∑x∈N|v| f(x) ≤ 1 for each v ∈ V (G), where N[v] is the closed neighborhood of v, then f is a signed 2-independence function on G. The weight of a signed 2-independence function f is w(f) =∑v∈V (G) f(v). The maximum of weights w(f), taken over all signed 2-independence functions f on G, is the signed 2-independence number α2s(G) of G. In this work, we mainly present upper bounds...

Minimal claw-free graphs

P. Dankelmann, Henda C. Swart, P. van den Berg, Wayne Goddard, M. D. Plummer (2008)

Czechoslovak Mathematical Journal

Similarity:

A graph G is a minimal claw-free graph (m.c.f. graph) if it contains no K 1 , 3 (claw) as an induced subgraph and if, for each edge e of G , G - e contains an induced claw. We investigate properties of m.c.f. graphs, establish sharp bounds on their orders and the degrees of their vertices, and characterize graphs which have m.c.f. line graphs.