اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدCharacterization of general position sets and its applications to cographs and bipartite graphs
122
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
A vertex subset $S$ of a graph $G$ is a general position set of $G$ if no vertex of $S$ lies on a geodesic between two other vertices of $S$. The cardinality of a largest general position set of $G$ is the general position number ${rm gp}(G)$ of $G$. It is proved that $Ssubseteq V(G)$ is in general position if and only if the components of $G[S]$ are complete subgraphs, the vertices of which form an in-transitive, distance-constant partition of $S$. If ${rm diam}(G) = 2$, then ${rm gp}(G)$ is the maximum of $omega(G)$ and the maximum order of an induced complete multipartite subgraph of the complement of $G$. As a consequence, ${rm gp}(G)$ of a cograph $G$ can be determined in polynomial time. If $G$ is bipartite, then ${rm gp}(G) leq alpha(G)$ with equality if ${rm diam}(G) in {2,3}$. A formula for the general position number of the complement of an arbitrary bipartite graph is deduced and simplified for the complements of trees, of grids, and of hypercubes.
قيم البحث
اقرأ أيضاً
Getting inspired by the famous no-three-in-line problem and by the general position subset selection problem from discrete geometry, the same is introduced into graph theory as follows. A set $S$ of vertices in a graph $G$ is a general position set i
f no element of $S$ lies on a geodesic between any two other elements of $S$. The cardinality of a largest general position set is the general position number ${rm gp}(G)$ of $G.$ In cite{ullas-2016} graphs $G$ of order $n$ with ${rm gp}(G)$ $in {2, n, n-1}$ were characterized. In this paper, we characterize the classes of all connected graphs of order $ngeq 4$ with the general position number $n-2.$
The general position number of a graph $G$ is the size of the largest set $K$ of vertices of $G$ such that no shortest path of $G$ contains three vertices of $K$. In this paper we discuss a related invariant, the monophonic position number, which is
obtained from the definition of general position number by replacing `shortest path with `induced path. We prove some basic properties of this invariant and determine the monophonic position number of several common types of graphs, including block graphs, unicyclic graphs, complements of bipartite graphs and split graphs. We present an upper bound for the monophonic position numbers of triangle-free graphs and use it to determine the monophonic position numbers of the Petersen graph and the Heawood graph. We then determine realisation results for the general position number, monophonic position number and monophonic hull number and finally find the monophonic position numbers of joins and corona products of graphs.
In this paper, based on the contributions of Tucker (1983) and Seb{H{o}} (1992), we generalize the concept of a sequential coloring of a graph to a framework in which the algorithm may use a coloring rule-base obtained from suitable forcing structure
s. In this regard, we introduce the {it weak} and {it strong sequential defining numbers} for such colorings and as the main results, after proving some basic properties, we show that these two parameters are intrinsically different and their spectra are nontrivial. Also, we consider the natural problems related to the complexity of computing such parameters and we show that in a variety of cases these problems are ${bf NP}$-complete. We conjecture that this result does not depend on the rule-base for all nontrivial cases.
Topological indices are a class of numerical invariants that predict certain physical and chemical properties of molecules. Recently, two novel topological indices, named as Sombor index and reduced Sombor index, were introduced by Gutman, defined as
$$SO(G)=sum_{uvin E(G)}sqrt{d_{G}^{2}(u)+d_{G}^{2}(v)},$$ $$SO_{red}(G)=sum_{uvin E(G)}sqrt{(d_{G}(u)-1)^{2}+(d_{G}(v)-1)^{2}},$$ where $d_{G}(u)$ denotes the degree of vertex $u$ in $G$. In this paper, our aim is to order the chemical trees, chemical unicyclic graphs, chemical bicyclic graphs and chemical tricyclic graphs with respect to Sombor index and reduced Sombor index. We determine the first fourteen minimum chemical trees, the first four minimum chemical unicyclic graphs, the first three minimum chemical bicyclic graphs, the first seven minimum chemical tricyclic graphs. At last, we consider the applications of reduced Sombor index to octane isomers.
For nonnegative integers $k, d_1, ldots, d_k$, a graph is $(d_1, ldots, d_k)$-colorable if its vertex set can be partitioned into $k$ parts so that the $i$th part induces a graph with maximum degree at most $d_i$ for all $iin{1, ldots, k}$. A class $
mathcal C$ of graphs is {it balanced $k$-partitionable} and {it unbalanced $k$-partitionable} if there exists a nonnegative integer $D$ such that all graphs in $mathcal C$ are $(D, ldots, D)$-colorable and $(0, ldots, 0, D)$-colorable, respectively, where the tuple has length $k$. A set $X$ of cycles is a {it cycle obstruction set} of a class $mathcal C$ of planar graphs if every planar graph containing none of the cycles in $X$ as a subgraph belongs to $mathcal C$. This paper characterizes all cycle obstruction sets of planar graphs to be balanced $k$-partitionable and unbalanced $k$-partitionable for all $k$; namely, we identify all inclusion-wise minimal cycle obstruction sets for all $k$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
