Page 1 Next

## Displaying 1 – 20 of 448

Showing per page

### 1-factorization of the Composition of Regular Graphs

Publications de l'Institut Mathématique

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

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-enumerations of halved alternating sign matrices.

Séminaire Lotharingien de Combinatoire [electronic only]

### 2-halvable complete 4-partite graphs

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 characterization of graphs in which some minimum dominating set covers all the edges

Czechoslovak Mathematical Journal

### A characterization of the decay number of a connected graph

Mathematica Slovaca

### A decomposition algorithm for the oriented adjacency graph of the triangulations of a bordered surface with marked points.

The Electronic Journal of Combinatorics [electronic only]

### A Décomposition Theorem on Euclidean Steiner Minimal Trees.

Discrete &amp; computational geometry

### A degree condition for the existence of $k$-factors with prescribed properties.

International Journal of Mathematics and Mathematical Sciences

### A direct decomposition of 3-connected planar graphs.

Séminaire Lotharingien de Combinatoire [electronic only]

### 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

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 forbidden subgraphs characterization and a polynomial algorithm for randomly decomposable graphs

Czechoslovak Mathematical Journal

### A generalization of Smith's theorem

Applicationes Mathematicae

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

Czechoslovak Mathematical Journal

The split graph ${K}_{r}+\overline{{K}_{s}}$ on $r+s$ vertices is denoted by ${S}_{r,s}$. A non-increasing sequence $\pi =\left({d}_{1},{d}_{2},...,{d}_{n}\right)$ of nonnegative integers is said to be potentially ${S}_{r,s}$-graphic if there exists a realization of $\pi$ containing ${S}_{r,s}$ as a subgraph. In this paper, we obtain a Havel-Hakimi type procedure and a simple sufficient condition for $\pi$ 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

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 matching and a Hamiltonian cycle of the fourth power of a connected graph

Mathematica Bohemica

The following result is proved: Let $G$ be a connected graph of order $geq4$. Then for every matching $M$ in ${G}^{4}$ there exists a hamiltonian cycle $C$ of ${G}^{4}$ such that $E\left(C\right)\bigcap M=0$.

### A Maximum Resonant Set of Polyomino Graphs

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

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...

### A Note on a Bermond's Conjecture

Publications de l'Institut Mathématique

### A Note On Analogies Between Characteristic And The Matching Polynomial Of A Graph

Publications de l'Institut Mathématique

Page 1 Next