A note on joins of additive hereditary graph properties

Ewa Drgas-Burchardt

Displaying similar documents to “A note on joins of additive hereditary graph properties”

Cardinality of a minimal forbidden graph family for reducible additive hereditary graph properties

Ewa Drgas-Burchardt (2009)

Discussiones Mathematicae Graph Theory

Similarity:

An additive hereditary graph property is any class of simple graphs, which is closed under isomorphisms unions and taking subgraphs. Let $L^{a}$ denote a class of all such properties. In the paper, we consider H-reducible over $L^{a}$ properties with H being a fixed graph. The finiteness of the sets of all minimal forbidden graphs is analyzed for such properties.

Graphs with small additive stretch number

Dieter Rautenbach (2004)

Discussiones Mathematicae Graph Theory

Similarity:

The additive stretch number $s_{a d d} (G)$ of a graph G is the maximum difference of the lengths of a longest induced path and a shortest induced path between two vertices of G that lie in the same component of G.We prove some properties of minimal forbidden configurations for the induced-hereditary classes of graphs G with $s_{a d d} (G) \leq k$ for some k ∈ N₀ = 0,1,2,.... Furthermore, we derive characterizations of these classes for k = 1 and k = 2.

Hyperreflexivity of bilattices

Kamila Kliś-Garlicka (2016)

Czechoslovak Mathematical Journal

Similarity:

The notion of a bilattice was introduced by Shulman. A bilattice is a subspace analogue for a lattice. In this work the definition of hyperreflexivity for bilattices is given and studied. We give some general results concerning this notion. To a given lattice $ℒ$ we can construct the bilattice $Σ_{ℒ}$ . Similarly, having a bilattice $Σ$ we may consider the lattice $ℒ_{Σ}$ . In this paper we study the relationship between hyperreflexivity of subspace lattices and of their associated bilattices. Some examples...

Iterated neighborhood graphs

Martin Sonntag, Hanns-Martin Teichert (2012)

Discussiones Mathematicae Graph Theory

Similarity:

The neighborhood graph N(G) of a simple undirected graph G = (V,E) is the graph $(V, E_{N})$ where $E_{N}$ = a,b | a ≠ b, x,a ∈ E and x,b ∈ E for some x ∈ V. It is well-known that the neighborhood graph N(G) is connected if and only if the graph G is connected and non-bipartite. We present some results concerning the k-iterated neighborhood graph $N^{k} (G) : = N (N (. . . N (G)))$ of G. In particular we investigate conditions for G and k such that $N^{k} (G)$ becomes a complete graph.

Intersection graph of gamma sets in the total graph

T. Tamizh Chelvam, T. Asir (2012)

Discussiones Mathematicae Graph Theory

Similarity:

In this paper, we consider the intersection graph $I_{Γ} (ℤ ₙ)$ of gamma sets in the total graph on ℤₙ. We characterize the values of n for which $I_{Γ} (ℤ ₙ)$ is complete, bipartite, cycle, chordal and planar. Further, we prove that $I_{Γ} (ℤ ₙ)$ is an Eulerian, Hamiltonian and as well as a pancyclic graph. Also we obtain the value of the independent number, the clique number, the chromatic number, the connectivity and some domination parameters of $I_{Γ} (ℤ ₙ)$ .

Remarks on partially square graphs, hamiltonicity and circumference

Hamamache Kheddouci (2001)

Discussiones Mathematicae Graph Theory

Similarity:

Given a graph G, its partially square graph G* is a graph obtained by adding an edge (u,v) for each pair u, v of vertices of G at distance 2 whenever the vertices u and v have a common neighbor x satisfying the condition $N_{G} (x) \subseteq N_{G} [u] \cup N_{G} [v]$ , where $N_{G} [x] = N_{G} (x) \cup x$ . In the case where G is a claw-free graph, G* is equal to G². We define $σ ° ₜ = m i n \sum_{x \in S} d_{G} (x) : S i s a n i n d e p e n d e n t s e t i n G * a n d | S | = t$ . We give for hamiltonicity and circumference new sufficient conditions depending on σ° and we improve some known results.

Potentially H-bigraphic sequences

Michael Ferrara, Michael Jacobson, John Schmitt, Mark Siggers (2009)

Discussiones Mathematicae Graph Theory

Similarity:

We extend the notion of a potentially H-graphic sequence as follows. Let A and B be nonnegative integer sequences. The sequence pair S = (A,B) is said to be bigraphic if there is some bipartite graph G = (X ∪ Y,E) such that A and B are the degrees of the vertices in X and Y, respectively. If S is a bigraphic pair, let σ(S) denote the sum of the terms in A. Given a bigraphic pair S, and a fixed bipartite graph H, we say that S is potentially H-bigraphic if there is some realization of...

Addendum to “On Meager Additive and Null Additive Sets in the Cantor space $2^{ω}$ and in ℝ” (Bull. Polish Acad. Sci. Math. 57 (2009), 91-99)

Tomasz Weiss (2014)

Bulletin of the Polish Academy of Sciences. Mathematics

Similarity:

We prove in ZFC that there is a set $A \subseteq 2^{ω}$ and a surjective function H: A → ⟨0,1⟩ such that for every null additive set X ⊆ ⟨0,1), $H^{- 1} (X)$ is null additive in $2^{ω}$ . This settles in the affirmative a question of T. Bartoszyński.

On the special context of independent sets

Vladimír Slezák (2001)

Discussiones Mathematicae - General Algebra and Applications

Similarity:

In this paper the context of independent sets $J_{L}^{p}$ is assigned to the complete lattice (P(M),⊆) of all subsets of a non-empty set M. Some properties of this context, especially the irreducibility and the span, are investigated.

On 𝓕-independence in graphs

Frank Göring, Jochen Harant, Dieter Rautenbach, Ingo Schiermeyer (2009)

Discussiones Mathematicae Graph Theory

Similarity:

Let be a set of graphs and for a graph G let $α_{} (G)$ and $α *_{} (G)$ denote the maximum order of an induced subgraph of G which does not contain a graph in as a subgraph and which does not contain a graph in as an induced subgraph, respectively. Lower bounds on $α_{} (G)$ and $α *_{} (G)$ are presented.

A note on the super-additive and sub-additive transformations of aggregation functions: The multi-dimensional case

Fateme Kouchakinejad, Alexandra Šipošová (2017)

Kybernetika

Similarity:

For an aggregation function $A$ we know that it is bounded by $A^{*}$ and $A_{*}$ which are its super-additive and sub-additive transformations, respectively. Also, it is known that if $A^{*}$ is directionally convex, then $A = A^{*}$ and $A_{*}$ is linear; similarly, if $A_{*}$ is directionally concave, then $A = A_{*}$ and $A^{*}$ is linear. We generalize these results replacing the directional convexity and concavity conditions by the weaker assumptions of overrunning a super-additive function and underrunning a sub-additive function, respectively. ...

Every lattice is embeddable in the lattice of $T_{1}$ -topologies

Richard Valent (1973)

Colloquium Mathematicae

Similarity:

On Meager Additive and Null Additive Sets in the Cantor Space $2^{ω}$ and in ℝ

Tomasz Weiss (2009)

Bulletin of the Polish Academy of Sciences. Mathematics

Similarity:

Let T be the standard Cantor-Lebesgue function that maps the Cantor space $2^{ω}$ onto the unit interval ⟨0,1⟩. We prove within ZFC that for every $X \subseteq 2^{ω}$ , X is meager additive in $2^{ω}$ iff T(X) is meager additive in ⟨0,1⟩. As a consequence, we deduce that the cartesian product of meager additive sets in ℝ remains meager additive in ℝ × ℝ. In this note, we also study the relationship between null additive sets in $2^{ω}$ and ℝ.

Special m-hyperidentities in biregular leftmost graph varieties of type (2,0)

Apinant Anantpinitwatna, Tiang Poomsa-ard (2009)

Discussiones Mathematicae - General Algebra and Applications

Similarity:

Graph algebras establish a connection between directed graphs without multiple edges and special universal algebras of type (2,0). We say that a graph G satisfies a term equation s ≈ t if the corresponding graph algebra $\underset{̲}{A (G)}$ satisfies s ≈ t. A class of graph algebras V is called a graph variety if $V = M o d_{g} Σ$ where Σ is a subset of T(X) × T(X). A graph variety $V^{'} = M o d_{g} Σ^{'}$ is called a biregular leftmost graph variety if Σ’ is a set of biregular leftmost term equations. A term equation s ≈ t is called an identity...

Upper oriented chromatic number of undirected graphs and oriented colorings of product graphs

Éric Sopena (2012)

Discussiones Mathematicae Graph Theory

Similarity:

The oriented chromatic number of an oriented graph $^{\to} G$ is the minimum order of an oriented graph $^{\to} H$ such that $^{\to} G$ admits a homomorphism to $^{\to} H$ . The oriented chromatic number of an undirected graph G is then the greatest oriented chromatic number of its orientations. In this paper, we introduce the new notion of the upper oriented chromatic number of an undirected graph G, defined as the minimum order of an oriented graph $^{\to} U$ such that every orientation $^{\to} G$ of G admits a homomorphism to $^{\to} U$ . We give...

Nonempty intersection of longest paths in a graph with a small matching number

Fuyuan Chen (2015)

Czechoslovak Mathematical Journal

Similarity:

A maximum matching of a graph $G$ is a matching of $G$ with the largest number of edges. The matching number of a graph $G$ , denoted by $α^{'} (G)$ , is the number of edges in a maximum matching of $G$ . In 1966, Gallai conjectured that all the longest paths of a connected graph have a common vertex. Although this conjecture has been disproved, finding some nice classes of graphs that support this conjecture is still very meaningful and interesting. In this short note, we prove that Gallai’s conjecture...