Page 1 Next

Displaying 1 – 20 of 445

Showing per page

1-factors and characterization of reducible faces of plane elementary bipartite graphs

Andrej Taranenko, Aleksander Vesel (2012)

Discussiones Mathematicae Graph Theory

As a general case of molecular graphs of benzenoid hydrocarbons, we study plane bipartite graphs with Kekulé structures (1-factors). A bipartite graph G is called elementary if G is connected and every edge belongs to a 1-factor of G. Some properties of the minimal and the maximal 1-factor of a plane elementary graph are given. A peripheral face f of a plane elementary graph is reducible, if the removal of the internal vertices and edges of the path that is the intersection of...

2-halvable complete 4-partite graphs

Dalibor Fronček (1998)

Discussiones Mathematicae Graph Theory

A complete 4-partite graph K m , m , m , m is called d-halvable if it can be decomposed into two isomorphic factors of diameter d. In the class of graphs K m , m , m , m with at most one odd part all d-halvable graphs are known. In the class of biregular graphs K m , m , m , m with four odd parts (i.e., the graphs K m , m , m , n and K m , m , n , n ) all d-halvable graphs are known as well, except for the graphs K m , m , n , n when d = 2 and n ≠ m. We prove that such graphs are 2-halvable iff n,m ≥ 3. We also determine a new class of non-halvable graphs K m , m , m , m with three or four different...

A Finite Characterization and Recognition of Intersection Graphs of Hypergraphs with Rank at Most 3 and Multiplicity at Most 2 in the Class of Threshold Graphs

Yury Metelsky, Kseniya Schemeleva, Frank Werner (2017)

Discussiones Mathematicae Graph Theory

We characterize the class [...] L32 L 3 2 of intersection graphs of hypergraphs with rank at most 3 and multiplicity at most 2 by means of a finite list of forbidden induced subgraphs in the class of threshold graphs. We also give an O(n)-time algorithm for the recognition of graphs from [...] L32 L 3 2 in the class of threshold graphs, where n is the number of vertices of a tested graph.

A Havel-Hakimi type procedure and a sufficient condition for a sequence to be potentially S r , s -graphic

Jian Hua Yin (2012)

Czechoslovak Mathematical Journal

The split graph K r + K s ¯ on r + s vertices is denoted by S r , s . A non-increasing sequence π = ( d 1 , d 2 , ... , d n ) of nonnegative integers is said to be potentially S r , s -graphic if there exists a realization of π containing S r , s as a subgraph. In this paper, we obtain a Havel-Hakimi type procedure and a simple sufficient condition for π to be potentially S r , s -graphic. They are extensions of two theorems due to A. R. Rao (The clique number of a graph with given degree sequence, Graph Theory, Proc. Symp., Calcutta 1976, ISI Lect. Notes Series...

A lower bound for the packing chromatic number of the Cartesian product of cycles

Yolandé Jacobs, Elizabeth Jonck, Ernst Joubert (2013)

Open Mathematics

Let G = (V, E) be a simple graph of order n and i be an integer with i ≥ 1. The set X i ⊆ V(G) is called an i-packing if each two distinct vertices in X i are more than i apart. A packing colouring of G is a partition X = {X 1, X 2, …, X k} of V(G) such that each colour class X i is an i-packing. The minimum order k of a packing colouring is called the packing chromatic number of G, denoted by χρ(G). In this paper we show, using a theoretical proof, that if q = 4t, for some integer t ≥ 3, then 9...

A Maximum Resonant Set of Polyomino Graphs

Heping Zhang, Xiangqian Zhou (2016)

Discussiones Mathematicae Graph Theory

A polyomino graph P is a connected finite subgraph of the infinite plane grid such that each finite face is surrounded by a regular square of side length one and each edge belongs to at least one square. A dimer covering of P corresponds to a perfect matching. Different dimer coverings can interact via an alternating cycle (or square) with respect to them. A set of disjoint squares of P is a resonant set if P has a perfect matching M so that each one of those squares is M-alternating. In this paper,...

A Neighborhood Condition for Fractional ID-[A, B]-Factor-Critical Graphs

Sizhong Zhou, Fan Yang, Zhiren Sun (2016)

Discussiones Mathematicae Graph Theory

Let G be a graph of order n, and let a and b be two integers with 1 ≤ a ≤ b. Let h : E(G) → [0, 1] be a function. If a ≤ ∑e∋x h(e) ≤ b holds for any x ∈ V (G), then we call G[Fh] a fractional [a, b]-factor of G with indicator function h, where Fh = {e ∈ E(G) : h(e) > 0}. A graph G is fractional independent-set-deletable [a, b]-factor-critical (in short, fractional ID-[a, b]- factor-critical) if G − I has a fractional [a, b]-factor for every independent set I of G. In this paper, it is proved...

Currently displaying 1 – 20 of 445

Page 1 Next