1-factorization of the Composition of Regular Graphs
1-factors and characterization of reducible faces of plane elementary bipartite graphs
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.
2-halvable complete 4-partite graphs
A complete 4-partite graph is called d-halvable if it can be decomposed into two isomorphic factors of diameter d. In the class of graphs with at most one odd part all d-halvable graphs are known. In the class of biregular graphs with four odd parts (i.e., the graphs and ) all d-halvable graphs are known as well, except for the graphs 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 with three or four different...
𝓟-bipartitions of minor hereditary properties
We prove that for any two minor hereditary properties 𝓟₁ and 𝓟₂, such that 𝓟₂ covers 𝓟₁, and for any graph G ∈ 𝓟₂ there is a 𝓟₁-bipartition of G. Some remarks on minimal reducible bounds are also included.
"Correction Of The Paper ""Graphs With Greatest Number Of Matchings"""
α-Labelings of a Class of Generalized Petersen Graphs
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 of decompositions...
-matroid and jump system.
Групповые раскраски полных двудольных графов и оценки чисел Хегквиста
Единичные и кратные покрытия графа ребрами
Конструирование графов
О покрытиях n-вершинных графов планарными, внешнепланарными и ациклическими подграфами