Unique factorization theorem

Peter Mihók

Displaying similar documents to “Unique factorization theorem”

Reducible properties of graphs

P. Mihók, G. Semanišin (1995)

Discussiones Mathematicae Graph Theory

Similarity:

Let L be the set of all hereditary and additive properties of graphs. For P₁, P₂ ∈ L, the reducible property R = P₁∘P₂ is defined as follows: G ∈ R if and only if there is a partition V(G) = V₁∪ V₂ of the vertex set of G such that $⟨ V ₁ ⟩_{G} \in P ₁$ and $⟨ V ₂ ⟩_{G} \in P ₂$ . The aim of this paper is to investigate the structure of the reducible properties of graphs with emphasis on the uniqueness of the decomposition of a reducible property into irreducible ones.

Factorizations of properties of graphs

Izak Broere, Samuel John Teboho Moagi, Peter Mihók, Roman Vasky (1999)

Discussiones Mathematicae Graph Theory

Similarity:

A property of graphs is any isomorphism closed class of simple graphs. For given properties of graphs ₁,₂,...,ₙ a vertex (₁, ₂, ...,ₙ)-partition of a graph G is a partition V₁,V₂,...,Vₙ of V(G) such that for each i = 1,2,...,n the induced subgraph $G [V_{i}]$ has property $_{i}$ . The class of all graphs having a vertex (₁, ₂, ...,ₙ)-partition is denoted by ₁∘₂∘...∘ₙ. A property is said to be reducible with respect to a lattice of properties of graphs if there are n ≥ 2 properties ₁,₂,...,ₙ ∈ such that...

Generalized edge-chromatic numbers and additive hereditary properties of graphs

Michael J. Dorfling, Samantha Dorfling (2002)

Discussiones Mathematicae Graph Theory

Similarity:

An additive hereditary property of graphs is a class of simple graphs which is closed under unions, subgraphs and isomorphisms. Let and be hereditary properties of graphs. The generalized edge-chromatic number $ρ_{}^{'} ()$ is defined as the least integer n such that ⊆ n. We investigate the generalized edge-chromatic numbers of the properties → H, ₖ, ₖ, *ₖ, ₖ and ₖ.

Generalized chromatic numbers and additive hereditary properties of graphs

Izak Broere, Samantha Dorfling, Elizabeth Jonck (2002)

Discussiones Mathematicae Graph Theory

Similarity:

An additive hereditary property of graphs is a class of simple graphs which is closed under unions, subgraphs and isomorphisms. Let and be additive hereditary properties of graphs. The generalized chromatic number $χ_{} ()$ is defined as follows: $χ_{} () = n$ iff ⊆ ⁿ but $⊊^{n - 1}$ . We investigate the generalized chromatic numbers of the well-known properties of graphs ₖ, ₖ, ₖ, ₖ and ₖ.

Criteria for of the existence of uniquely partitionable graphs with respect to additive induced-hereditary properties

Izak Broere, Jozef Bucko, Peter Mihók (2002)

Discussiones Mathematicae Graph Theory

Similarity:

Let ₁,₂,...,ₙ be graph properties, a graph G is said to be uniquely (₁,₂, ...,ₙ)-partitionable if there is exactly one (unordered) partition V₁,V₂,...,Vₙ of V(G) such that $G [V_{i}] \in_{i}$ for i = 1,2,...,n. We prove that for additive and induced-hereditary properties uniquely (₁,₂,...,ₙ)-partitionable graphs exist if and only if $_{i}$ and $_{j}$ are either coprime or equal irreducible properties of graphs for every i ≠ j, i,j ∈ 1,2,...,n.

The decomposability of additive hereditary properties of graphs

Izak Broere, Michael J. Dorfling (2000)

Discussiones Mathematicae Graph Theory

Similarity:

An additive hereditary property of graphs is a class of simple graphs which is closed under unions, subgraphs and isomorphisms. If ₁,...,ₙ are properties of graphs, then a (₁,...,ₙ)-decomposition of a graph G is a partition E₁,...,Eₙ of E(G) such that $G [E_{i}]$ , the subgraph of G induced by $E_{i}$ , is in $_{i}$ , for i = 1,...,n. We define ₁ ⊕...⊕ ₙ as the property G ∈ : G has a (₁,...,ₙ)-decomposition. A property is said to be decomposable if there exist non-trivial hereditary properties ₁ and ₂ such...

Bounding the Openk-Monopoly Number of Strong Product Graphs

Dorota Kuziak, Iztok Peterin, Ismael G. Yero (2018)

Discussiones Mathematicae Graph Theory

Similarity:

Let G = (V, E) be a simple graph without isolated vertices and minimum degree δ, and let k ∈ 1 − ⌈δ/2⌉, . . . , ⌊δ/2⌋ be an integer. Given a set M ⊂ V, a vertex v of G is said to be k-controlled by M if [...] δM(v)≥δG(v)2+k $δ_{M} (v) \geq \frac{δ_{G} (v)}{2} + k$ , where δM(v) represents the number of neighbors of v in M and δG(v) the degree of v in G. A set M is called an open k-monopoly if every vertex v of G is k-controlled by M. The minimum cardinality of any open k-monopoly is the open k-monopoly number of G. In this...

Minimal forbidden subgraphs of reducible graph properties

Amelie J. Berger (2001)

Discussiones Mathematicae Graph Theory

Similarity:

A property of graphs is any class of graphs closed under isomorphism. Let ₁,₂,...,ₙ be properties of graphs. A graph G is (₁,₂,...,ₙ)-partitionable if the vertex set V(G) can be partitioned into n sets, V₁,V₂,..., Vₙ, such that for each i = 1,2,...,n, the graph $G [V_{i}] \in_{i}$ . We write ₁∘₂∘...∘ₙ for the property of all graphs which have a (₁,₂,...,ₙ)-partition. An additive induced-hereditary property is called reducible if there exist additive induced-hereditary properties ₁ and ₂ such that = ₁∘₂....

Uniquely partitionable planar graphs with respect to properties having a forbidden tree

Jozef Bucko, Jaroslav Ivančo (1999)

Discussiones Mathematicae Graph Theory

Similarity:

Let ₁, ₂ be graph properties. A vertex (₁,₂)-partition of a graph G is a partition V₁,V₂ of V(G) such that for i = 1,2 the induced subgraph $G [V_{i}]$ has the property $_{i}$ . A property ℜ = ₁∘₂ is defined to be the set of all graphs having a vertex (₁,₂)-partition. A graph G ∈ ₁∘₂ is said to be uniquely (₁,₂)-partitionable if G has exactly one vertex (₁,₂)-partition. In this note, we show the existence of uniquely partitionable planar graphs with respect to hereditary additive properties having a...

The order of uniquely partitionable graphs

Izak Broere, Marietjie Frick, Peter Mihók (1997)

Discussiones Mathematicae Graph Theory

Similarity:

Let ₁,...,ₙ be properties of graphs. A (₁,...,ₙ)-partition of a graph G is a partition V₁,...,Vₙ of V(G) such that, for each i = 1,...,n, the subgraph of G induced by $V_{i}$ has property $_{i}$ . If a graph G has a unique (₁,...,ₙ)-partition we say it is uniquely (₁,...,ₙ)-partitionable. We establish best lower bounds for the order of uniquely (₁,...,ₙ)-partitionable graphs, for various choices of ₁,...,ₙ.

On hereditary properties of composition graphs

Vadim E. Levit, Eugen Mandrescu (1998)

Discussiones Mathematicae Graph Theory

Similarity:

The composition graph of a family of n+1 disjoint graphs $H_{i} : 0 \leq i \leq n$ is the graph H obtained by substituting the n vertices of H₀ respectively by the graphs H₁,H₂,...,Hₙ. If H has some hereditary property P, then necessarily all its factors enjoy the same property. For some sort of graphs it is sufficient that all factors $H_{i} : 0 \leq i \leq n$ have a certain common P to endow H with this P. For instance, it is known that the composition graph of a family of perfect graphs is also a perfect graph (B. Bollobas, 1978),...

Clopen graphs

Stefan Geschke (2013)

Fundamenta Mathematicae

Similarity:

A graph G on a topological space X as its set of vertices is clopen if the edge relation of G is a clopen subset of X² without the diagonal. We study clopen graphs on Polish spaces in terms of their finite induced subgraphs and obtain information about their cochromatic numbers. In this context we investigate modular profinite graphs, a class of graphs obtained from finite graphs by taking inverse limits. This continues the investigation of continuous colorings on Polish spaces and their...

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

Similarity:

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.

Uniquely partitionable graphs

Jozef Bucko, Marietjie Frick, Peter Mihók, Roman Vasky (1997)

Discussiones Mathematicae Graph Theory

Similarity:

Let ₁,...,ₙ be properties of graphs. A (₁,...,ₙ)-partition of a graph G is a partition of the vertex set V(G) into subsets V₁, ...,Vₙ such that the subgraph $G [V_{i}]$ induced by $V_{i}$ has property $_{i}$ ; i = 1,...,n. A graph G is said to be uniquely (₁, ...,ₙ)-partitionable if G has exactly one (₁,...,ₙ)-partition. A property is called hereditary if every subgraph of every graph with property also has property . If every graph that is a disjoint union of two graphs that have property also has property...

Structure of the set of all minimal total dominating functions of some classes of graphs

K. Reji Kumar, Gary MacGillivray (2010)

Discussiones Mathematicae Graph Theory

Similarity:

In this paper we study some of the structural properties of the set of all minimal total dominating functions ( $_{T}$ ) of cycles and paths and introduce the idea of function reducible graphs and function separable graphs. It is proved that a function reducible graph is a function separable graph. We shall also see how the idea of function reducibility is used to study the structure of $_{T} (G)$ for some classes of graphs.

Maximal graphs with respect to hereditary properties

Izak Broere, Marietjie Frick, Gabriel Semanišin (1997)

Discussiones Mathematicae Graph Theory

Similarity:

A property of graphs is a non-empty set of graphs. A property P is called hereditary if every subgraph of any graph with property P also has property P. Let P₁, ...,Pₙ be properties of graphs. We say that a graph G has property P₁∘...∘Pₙ if the vertex set of G can be partitioned into n sets V₁, ...,Vₙ such that the subgraph of G induced by Vi has property $P_{i}$ ; i = 1,..., n. A hereditary property R is said to be reducible if there exist two hereditary properties P₁ and P₂ such that R =...

Symmetries of embedded complete bipartite graphs

Erica Flapan, Nicole Lehle, Blake Mellor, Matt Pittluck, Xan Vongsathorn (2014)

Fundamenta Mathematicae

Similarity:

We characterize which automorphisms of an arbitrary complete bipartite graph $K_{n, m}$ can be induced by a homeomorphism of some embedding of the graph in S³.

The hull number of strong product graphs

A.P. Santhakumaran, S.V. Ullas Chandran (2011)

Discussiones Mathematicae Graph Theory

Similarity:

For a connected graph G with at least two vertices and S a subset of vertices, the convex hull ${[S]}_{G}$ is the smallest convex set containing S. The hull number h(G) is the minimum cardinality among the subsets S of V(G) with ${[S]}_{G} = V (G)$ . Upper bound for the hull number of strong product G ⊠ H of two graphs G and H is obtainted. Improved upper bounds are obtained for some class of strong product graphs. Exact values for the hull number of some special classes of strong product graphs are obtained. Graphs...

Gallai's innequality for critical graphs of reducible hereditary properties

Peter Mihók, Riste Skrekovski (2001)

Discussiones Mathematicae Graph Theory

Similarity:

In this paper Gallai’s inequality on the number of edges in critical graphs is generalized for reducible additive induced-hereditary properties of graphs in the following way. Let $₁, ₂, . . ., ₖ$ (k ≥ 2) be additive induced-hereditary properties, $= ₁ \circ ₂ \circ . . . \circ ₖ$ and $δ = \sum_{i = 1}^{k} δ (_{i})$ . Suppose that G is an -critical graph with n vertices and m edges. Then 2m ≥ δn + (δ-2)/(δ²+2δ-2)*n + (2δ)/(δ²+2δ-2) unless = ² or $G = K_{δ + 1}$ . The generalization of Gallai’s inequality for -choice critical graphs is also presented.

Radio numbers for generalized prism graphs

Paul Martinez, Juan Ortiz, Maggy Tomova, Cindy Wyels (2011)

Discussiones Mathematicae Graph Theory

Similarity:

A radio labeling is an assignment c:V(G) → N such that every distinct pair of vertices u,v satisfies the inequality d(u,v) + |c(u)-c(v)| ≥ diam(G) + 1. The span of a radio labeling is the maximum value. The radio number of G, rn(G), is the minimum span over all radio labelings of G. Generalized prism graphs, denoted $Z_{n, s}$ , s ≥ 1, n ≥ s, have vertex set (i,j) | i = 1,2 and j = 1,...,n and edge set ((i,j),(i,j ±1)) ∪ ((1,i),(2,i+σ)) | σ = -⌊(s-1)/2⌋...,0,...,⌊s/2⌋. In this paper we determine...

On the minimal basis of the spindle-surface $g e r m S_{1}$ .

R. Bodendiek, K. Wagner (1989)

Banach Center Publications

Similarity:

On 2-periodic graphs of a certain graph operator

Ivan Havel, Bohdan Zelinka (2001)

Discussiones Mathematicae Graph Theory

Similarity:

We deal with the graph operator $\bar{P o w ₂}$ defined to be the complement of the square of a graph: $\bar{P o w ₂} (G) = \bar{P o w ₂ (G)}$ . Motivated by one of many open problems formulated in [6] we look for graphs that are 2-periodic with respect to this operator. We describe a class of bipartite graphs possessing the above mentioned property and prove that for any m,n ≥ 6, the complete bipartite graph $K_{m, n}$ can be decomposed in two edge-disjoint factors from . We further show that all the incidence graphs of Desarguesian finite projective...

Rotation and jump distances between graphs

Gary Chartrand, Heather Gavlas, Héctor Hevia, Mark A. Johnson (1997)

Discussiones Mathematicae Graph Theory

Similarity:

A graph H is obtained from a graph G by an edge rotation if G contains three distinct vertices u,v, and w such that uv ∈ E(G), uw ∉ E(G), and H = G-uv+uw. A graph H is obtained from a graph G by an edge jump if G contains four distinct vertices u,v,w, and x such that uv ∈ E(G), wx∉ E(G), and H = G-uv+wx. If a graph H is obtained from a graph G by a sequence of edge jumps, then G is said to be j-transformed into H. It is shown that for every two graphs G and H of the same order (at least...

2-halvable complete 4-partite graphs

Dalibor Fronček (1998)

Discussiones Mathematicae Graph Theory

Similarity:

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