Unicyclic graphs with bicyclic inverses

Swarup Kumar Panda

Displaying similar documents to “Unicyclic graphs with bicyclic inverses”

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.

On characterization of uniquely 3-list colorable complete multipartite graphs

Yancai Zhao, Erfang Shan (2010)

Discussiones Mathematicae Graph Theory

Similarity:

For each vertex v of a graph G, if there exists a list of k colors, L(v), such that there is a unique proper coloring for G from this collection of lists, then G is called a uniquely k-list colorable graph. Ghebleh and Mahmoodian characterized uniquely 3-list colorable complete multipartite graphs except for nine graphs: $K_{2, 2, r}$ r ∈ 4,5,6,7,8, $K_{2, 3, 4}$ , $K_{1 * 4, 4}$ , $K_{1 * 4, 5}$ , $K_{1 * 5, 4}$ . Also, they conjectured that the nine graphs are not U3LC graphs. After that, except for $K_{2, 2, r}$ r ∈ 4,5,6,7,8, the others have been proved not...

Generalized connectivity of some total graphs

Yinkui Li, Yaping Mao, Zhao Wang, Zongtian Wei (2021)

Czechoslovak Mathematical Journal

Similarity:

We study the generalized $k$ -connectivity $κ_{k} (G)$ as introduced by Hager in 1985, as well as the more recently introduced generalized $k$ -edge-connectivity $λ_{k} (G)$ . We determine the exact value of $κ_{k} (G)$ and $λ_{k} (G)$ for the line graphs and total graphs of trees, unicyclic graphs, and also for complete graphs for the case $k = 3$ .

Paired domination in prisms of graphs

Christina M. Mynhardt, Mark Schurch (2011)

Discussiones Mathematicae Graph Theory

Similarity:

The paired domination number $γ_{p r} (G)$ of a graph G is the smallest cardinality of a dominating set S of G such that ⟨S⟩ has a perfect matching. The generalized prisms πG of G are the graphs obtained by joining the vertices of two disjoint copies of G by |V(G)| independent edges. We provide characterizations of the following three classes of graphs: $γ_{p r} (π G) = 2 γ_{p r} (G)$ for all πG; $γ_{p r} (K ₂ ☐ G) = 2 γ_{p r} (G)$ ; $γ_{p r} (K ₂ ☐ G) = γ_{p r} (G)$ .

Remarks on $D$ -integral complete multipartite graphs

Pavel Híc, Milan Pokorný (2016)

Czechoslovak Mathematical Journal

Similarity:

A graph is called distance integral (or $D$ -integral) if all eigenvalues of its distance matrix are integers. In their study of $D$ -integral complete multipartite graphs, Yang and Wang (2015) posed two questions on the existence of such graphs. We resolve these questions and present some further results on $D$ -integral complete multipartite graphs. We give the first known distance integral complete multipartite graphs $K_{p_{1}, p_{2}, p_{3}}$ with $p_{1} < p_{2} < p_{3}$ , and $K_{p_{1}, p_{2}, p_{3}, p_{4}}$ with $p_{1} < p_{2} < p_{3} < p_{4}$ , as well as the infinite classes of distance integral...

The spectral determinations of the connected multicone graphs $K_{w} ▽ m P_{17}$ and $K_{w} ▽ m S$

Ali Zeydi Abdian, S. Morteza Mirafzal (2018)

Czechoslovak Mathematical Journal

Similarity:

Finding and discovering any class of graphs which are determined by their spectra is always an important and interesting problem in the spectral graph theory. The main aim of this study is to characterize two classes of multicone graphs which are determined by both their adjacency and Laplacian spectra. A multicone graph is defined to be the join of a clique and a regular graph. Let $K_{w}$ denote a complete graph on $w$ vertices, and let $m$ be a positive integer number. In A. Z. Abdian (2016)...

4-cycle properties for characterizing rectagraphs and hypercubes

Khadra Bouanane, Abdelhafid Berrachedi (2017)

Czechoslovak Mathematical Journal

Similarity:

A $(0, 2)$ -graph is a connected graph, where each pair of vertices has either 0 or 2 common neighbours. These graphs constitute a subclass of $(0, λ)$ -graphs introduced by Mulder in 1979. A rectagraph, well known in diagram geometry, is a triangle-free $(0, 2)$ -graph. $(0, 2)$ -graphs include hypercubes, folded cube graphs and some particular graphs such as icosahedral graph, Shrikhande graph, Klein graph, Gewirtz graph, etc. In this paper, we give some local properties of 4-cycles in $(0, λ)$ -graphs and more specifically...

Decomposition of Cartesian product of complete graphs into paths and stars with four edges

Arockiajeyaraj P. Ezhilarasi, Appu Muthusamy (2021)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

Let $P_{k}$ and $S_{k}$ denote a path and a star, respectively, on $k$ vertices. We give necessary and sufficient conditions for the existence of a complete ${P_{5}, S_{5}}$ -decomposition of Cartesian product of complete graphs.

Proper connection number of bipartite graphs

Jun Yue, Meiqin Wei, Yan Zhao (2018)

Czechoslovak Mathematical Journal

Similarity:

An edge-colored graph $G$ is proper connected if every pair of vertices is connected by a proper path. The proper connection number of a connected graph $G$ , denoted by $pc (G)$ , is the smallest number of colors that are needed to color the edges of $G$ in order to make it proper connected. In this paper, we obtain the sharp upper bound for $pc (G)$ of a general bipartite graph $G$ and a series of extremal graphs. Additionally, we give a proper $2$ -coloring for a connected bipartite graph $G$ having $δ (G) \geq 2$ and a dominating...

The extremal irregularity of connected graphs with given number of pendant vertices

Xiaoqian Liu, Xiaodan Chen, Junli Hu, Qiuyun Zhu (2022)

Czechoslovak Mathematical Journal

Similarity:

The irregularity of a graph $G = (V, E)$ is defined as the sum of imbalances $| d_{u} - d_{v} |$ over all edges $u v \in E$ , where $d_{u}$ denotes the degree of the vertex $u$ in $G$ . This graph invariant, introduced by Albertson in 1997, is a measure of the defect of regularity of a graph. In this paper, we completely determine the extremal values of the irregularity of connected graphs with $n$ vertices and $p$ pendant vertices ( $1 \leq p \leq n - 1$ ), and characterize the corresponding extremal graphs.

Characterization by intersection graph of some families of finite nonsimple groups

Hossein Shahsavari, Behrooz Khosravi (2021)

Czechoslovak Mathematical Journal

Similarity:

For a finite group $G$ , $Γ (G)$ , the intersection graph of $G$ , is a simple graph whose vertices are all nontrivial proper subgroups of $G$ and two distinct vertices $H$ and $K$ are adjacent when $H \cap K \neq 1$ . In this paper, we classify all finite nonsimple groups whose intersection graphs have a leaf and also we discuss the characterizability of them using their intersection graphs.

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

A note on the independent domination number versus the domination number in bipartite graphs

Shaohui Wang, Bing Wei (2017)

Czechoslovak Mathematical Journal

Similarity:

Let $γ (G)$ and $i (G)$ be the domination number and the independent domination number of $G$ , respectively. Rad and Volkmann posted a conjecture that $i (G) / γ (G) \leq Δ (G) / 2$ for any graph $G$ , where $Δ (G)$ is its maximum degree (see N. J. Rad, L. Volkmann (2013)). In this work, we verify the conjecture for bipartite graphs. Several graph classes attaining the extremal bound and graphs containing odd cycles with the ratio larger than $Δ (G) / 2$ are provided as well.