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

Apinant Anantpinitwatna; Tiang Poomsa-ard

Displaying similar documents to “Special m-hyperidentities in biregular leftmost graph varieties of type (2,0)”

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.

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

On the diameter of the intersection graph of a finite simple group

Xuanlong Ma (2016)

Czechoslovak Mathematical Journal

Similarity:

Let $G$ be a finite group. The intersection graph $Δ_{G}$ of $G$ is an undirected graph without loops and multiple edges defined as follows: the vertex set is the set of all proper nontrivial subgroups of $G$ , and two distinct vertices $X$ and $Y$ are adjacent if $X \cap Y \neq 1$ , where $1$ denotes the trivial subgroup of order $1$ . A question was posed by Shen (2010) whether the diameters of intersection graphs of finite non-abelian simple groups have an upper bound. We answer the question and show that the diameters...

Some remarks on α-domination

Franz Dahme, Dieter Rautenbach, Lutz Volkmann (2004)

Discussiones Mathematicae Graph Theory

Similarity:

Let α ∈ (0,1) and let $G = (V_{G}, E_{G}$ ) be a graph. According to Dunbar, Hoffman, Laskar and Markus [3] a set $D \subseteq V_{G}$ is called an α-dominating set of G, if $| N_{G} (u) \cap D | \geq α d_{G} (u)$ for all $u \in V_{G} ∖ D$ . We prove a series of upper bounds on the α-domination number of a graph G defined as the minimum cardinality of an α-dominating set of G.

Domination and independence subdivision numbers of graphs

Teresa W. Haynes, Sandra M. Hedetniemi, Stephen T. Hedetniemi (2000)

Discussiones Mathematicae Graph Theory

Similarity:

The domination subdivision number $s d_{γ} (G)$ of a graph is the minimum number of edges that must be subdivided (where an edge can be subdivided at most once) in order to increase the domination number. Arumugam showed that this number is at most three for any tree, and conjectured that the upper bound of three holds for any graph. Although we do not prove this interesting conjecture, we give an upper bound for the domination subdivision number for any graph G in terms of the minimum degrees of...

Classification of rings with toroidal Jacobson graph

Krishnan Selvakumar, Manoharan Subajini (2016)

Czechoslovak Mathematical Journal

Similarity:

Let $R$ be a commutative ring with nonzero identity and $J (R)$ the Jacobson radical of $R$ . The Jacobson graph of $R$ , denoted by $𝔍_{R}$ , is defined as the graph with vertex set $R ∖ J (R)$ such that two distinct vertices $x$ and $y$ are adjacent if and only if $1 - x y$ is not a unit of $R$ . The genus of a simple graph $G$ is the smallest nonnegative integer $n$ such that $G$ can be embedded into an orientable surface $S_{n}$ . In this paper, we investigate the genus number of the compact Riemann surface in which $𝔍_{R}$ can be embedded and...

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

The prime ideals intersection graph of a ring

M. J. Nikmehr, B. Soleymanzadeh (2017)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

Let $R$ be a commutative ring with unity and $U (R)$ be the set of unit elements of $R$ . In this paper, we introduce and investigate some properties of a new kind of graph on the ring $R$ , namely, the prime ideals intersection graph of $R$ , denoted by $G_{p} (R)$ . The $G_{p} (R)$ is a graph with vertex set $R^{*} - U (R)$ and two distinct vertices $a$ and $b$ are adjacent if and only if there exists a prime ideal $𝔭$ of $R$ such that $a, b \in 𝔭$ . We obtain necessary and sufficient conditions on $R$ such that $G_{p} (R)$ is disconnected. We find the diameter and...

Edge-colouring of graphs and hereditary graph properties

Samantha Dorfling, Tomáš Vetrík (2016)

Czechoslovak Mathematical Journal

Similarity:

Edge-colourings of graphs have been studied for decades. We study edge-colourings with respect to hereditary graph properties. For a graph $G$ , a hereditary graph property $𝒫$ and $l \geq 1$ we define $χ_{𝒫, l}^{'} (G)$ to be the minimum number of colours needed to properly colour the edges of $G$ , such that any subgraph of $G$ induced by edges coloured by (at most) $l$ colours is in $𝒫$ . We present a necessary and sufficient condition for the existence of $χ_{𝒫, l}^{'} (G)$ . We focus on edge-colourings of graphs with respect to the hereditary...

A co-ideal based identity-summand graph of a commutative semiring

S. Ebrahimi Atani, S. Dolati Pish Hesari, M. Khoramdel (2015)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

Let $I$ be a strong co-ideal of a commutative semiring $R$ with identity. Let $Γ_{I} (R)$ be a graph with the set of vertices $S_{I} (R) = {x \in R ∖ I : x + y \in I$ for some $y \in R ∖ I}$ , where two distinct vertices $x$ and $y$ are adjacent if and only if $x + y \in I$ . We look at the diameter and girth of this graph. Also we discuss when $Γ_{I} (R)$ is bipartite. Moreover, studies are done on the planarity, clique, and chromatic number of this graph. Examples illustrating the results are presented.

The chromatic equivalence class of graph $\bar{B_{n - 6, 1, 2}}$

Jianfeng Wang, Qiongxiang Huang, Chengfu Ye, Ruying Liu (2008)

Discussiones Mathematicae Graph Theory

Similarity:

By h(G,x) and P(G,λ) we denote the adjoint polynomial and the chromatic polynomial of graph G, respectively. A new invariant of graph G, which is the fourth character R₄(G), is given in this paper. Using the properties of the adjoint polynomials, the adjoint equivalence class of graph $B_{n - 6, 1, 2}$ is determined, which can be regarded as the continuance of the paper written by Wang et al. [J. Wang, R. Liu, C. Ye and Q. Huang, A complete solution to the chromatic equivalence class of graph $\bar{B_{n - 7, 1, 3}}$ , Discrete...

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_{Γ} (ℤ ₙ)$ .

Some results on the annihilator graph of a commutative ring

Mojgan Afkhami, Kazem Khashyarmanesh, Zohreh Rajabi (2017)

Czechoslovak Mathematical Journal

Similarity:

Let $R$ be a commutative ring. The annihilator graph of $R$ , denoted by $AG (R)$ , is the undirected graph with all nonzero zero-divisors of $R$ as vertex set, and two distinct vertices $x$ and $y$ are adjacent if and only if ${ann}_{R} (x y) \neq {ann}_{R} (x) \cup {ann}_{R} (y)$ , where for $z \in R$ , ${ann}_{R} (z) = {r \in R : r z = 0}$ . In this paper, we characterize all finite commutative rings $R$ with planar or outerplanar or ring-graph annihilator graphs. We characterize all finite commutative rings $R$ whose annihilator graphs have clique number $1$ , $2$ or $3$ . Also, we investigate some properties...