Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn monophonic position sets in graphs
65
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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.
The general position number of a graph $G$ is the size of the largest set of vertices $S$ such that no geodesic of $G$ contains more than two elements of $S$. The monophonic position number of a graph is defined similarly, but with `induced path in place of `geodesic. In this paper we investigate some extremal problems for these parameters. Firstly we discuss the problem of the smallest possible order of a graph with given general and monophonic position numbers, with applications to a realisation result. We then solve a Tur{a}n problem for the size of graphs with given order and position numbers and characterise the possible diameters of graphs with given order and monophonic position number. Finally we classify the graphs with given order and diameter and largest possible general position number.
In this paper, we study independent domination in directed graphs, which was recently introduced by Cary, Cary, and Prabhu. We provide a short, algorithmic proof that all directed acyclic graphs contain an independent dominating set. Using linear algebraic tools, we prove that any strongly connected graph with even period has at least two independent dominating sets, generalizing several of the results of Cary, Cary, and Prabhu. We prove that determining the period of the graph is not sufficient to determine the existence of an independent dominating set by constructing a few examples of infinite families of graphs. We show that the direct analogue of Vizings Conjecture does not hold for independent domination number in directed graphs by providing two infinite families of graphs. We initialize the study of time complexity for independent domination in directed graphs, proving that the existence of an independent dominating set in directed acyclic graphs and strongly connected graphs with even period are in the time complexity class $P$. We also provide an algorithm for determining existence of an independent dominating set for digraphs with period greater than $1$.
The notion of a Riordan graph was introduced recently, and it is a far-reaching generalization of the well-known Pascal graphs and Toeplitz graphs. However, apart from a certain subclass of Toeplitz graphs, nothing was known on independent sets in Riordan graphs. In this paper, we give exact enumeration and lower and upper bounds for the number of independent sets for various classes of Riordan graphs. Remarkably, we offer a variety of methods to solve the problems that range from the structural decomposition theorem to methods in combinatorics on words. Some of our results are valid for any graph.
We prove an asymptotically tight lower bound on the average size of independent sets in a triangle-free graph on $n$ vertices with maximum degree $d$, showing that an independent set drawn uniformly at random from such a graph has expected size at least $(1+o_d(1)) frac{log d}{d}n$. This gives an alternative proof of Shearers upper bound on the Ramsey number $R(3,k)$. We then prove that the total number of independent sets in a triangle-free graph with maximum degree $d$ is at least $exp left[left(frac{1}{2}+o_d(1) right) frac{log^2 d}{d}n right]$. The constant $1/2$ in the exponent is best possible. In both cases, tightness is exhibited by a random $d$-regular graph. Both results come from considering the hard-core model from statistical physics: a random independent set $I$ drawn from a graph with probability proportional to $lambda^{|I|}$, for a fugacity parameter $lambda>0$. We prove a general lower bound on the occupancy fraction (normalized expected size of the random independent set) of the hard-core model on triangle-free graphs of maximum degree $d$. The bound is asymptotically tight in $d$ for all $lambda =O_d(1)$. We conclude by stating several conjectures on the relationship between the average and maximum size of an independent set in a triangle-free graph and give some consequences of these conjectures in Ramsey theory.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
