Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCharacterization of Graphs with Villainy 2
56
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Let $f$ be an optimal proper coloring of a graph $G$ and let $c$ be a coloring of the vertices of $G$ obtained by permuting the colors on vertices in the proper coloring $f$. The villainy of $c$, written $B(c)$, is the minimum number of vertices that must be recolored to obtain a proper coloring of $G$ with the additional condition that the number of times each color is used does not change. The villainy of $G$ is defined as $B(G)=max_{c}B(c)$, over all optimal proper colorings of $G$. In this paper, we characterize graphs $G$ with $B(G)=2$.
rate research
Read More
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 if 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.$
Let $P_n$ and $C_n$ denote the path and cycle on $n$ vertices respectively. The dumbbell graph, denoted by $D_{p,k,q}$, is the graph obtained from two cycles $C_p$, $C_q$ and a path $P_{k+2}$ by identifying each pendant vertex of $P_{k+2}$ with a vertex of a cycle respectively. The theta graph, denoted by $Theta_{r,s,t}$, is the graph formed by joining two given vertices via three disjoint paths $P_{r}$, $P_{s}$ and $P_{t}$ respectively. In this paper, we prove that all dumbbell graphs as well as theta graphs are determined by their Laplacian spectra.
Let $G=(V,E)$ be a finite undirected graph. Orient the edges of $G$ in an arbitrary way. A $2$-cycle on $G$ is a function $d : E^2to mathbb{Z}$ such for each edge $e$, $d(e, cdot)$ and $d(cdot, e)$ are circulations on $G$, and $d(e, f) = 0$ whenever $e$ and $f$ have a common vertex. We show that each $2$-cycle is a sum of three special types of $2$-cycles: cycle-pair $2$-cycles, Kuratowski $2$-cycles, and quad $2$-cycles. In case that the graph is Kuratowski connected, we show that each $2$-cycle is a sum of cycle-pair $2$-cycles and at most one Kuratowski $2$-cycle. Furthermore, if $G$ is Kuratowski connected, we characterize when every Kuratowski $2$-cycle is a sum of cycle-pair $2$-cycles. A $2$-cycles $d$ on $G$ is skew-symmetric if $d(e,f) = -d(f,e)$ for all edges $e,fin E$. We show that each $2$-cycle is a sum of two special types of skew-symmetric $2$-cycles: skew-symmetric cycle-pair $2$-cycles and skew-symmetric quad $2$-cycles. In case that the graph is Kuratowski connected, we show that each skew-symmetric $2$-cycle is a sum of skew-symmetric cycle-pair $2$-cycles. Similar results like this had previously been obtained by one of the authors for symmetric $2$-cycles. Symmetric $2$-cycles are $2$-cycles $d$ such that $d(e,f)=d(f,e)$ for all edges $e,fin E$.
Let $k$ be a positive integer, and $G$ be a $k$-connected graph. An edge-coloured path is emph{rainbow} if all of its edges have distinct colours. The emph{rainbow $k$-connection number} of $G$, denoted by $rc_k(G)$, is the minimum number of colours in an edge-colouring of $G$ such that, any two vertices are connected by $k$ internally vertex-disjoint rainbow paths. The function $rc_k(G)$ was introduced by Chartrand, Johns, McKeon and Zhang in 2009, and has since attracted significant interest. Let $t_k(n,r)$ denote the minimum number of edges in a $k$-connected graph $G$ on $n$ vertices with $rc_k(G)le r$. Let $s_k(n,r)$ denote the maximum number of edges in a $k$-connected graph $G$ on $n$ vertices with $rc_k(G)ge r$. The functions $t_1(n,r)$ and $s_1(n,r)$ have previously been studied by various authors. In this paper, we study the functions $t_2(n,r)$ and $s_2(n,r)$. We determine bounds for $t_2(n,r)$ which imply that $t_2(n,2)=(1+o(1))nlog_2 n$, and $t_2(n,r)$ is linear in $n$ for $rge 3$. We also provide some remarks about the function $s_2(n,r)$.
We consider pressing sequences, a certain kind of transformation of graphs with loops into empty graphs, motivated by an application in phylogenetics. In particular, we address the question of when a graph has precisely one such pressing sequence, thus answering an question from Cooper and Davis (2015). We characterize uniquely pressable graphs, count the number of them on a given number of vertices, and provide a polynomial time recognition algorithm. We conclude with a few open questions. Keywords: Pressing sequence, adjacency matrix, Cholesky factorization, binary matrix
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
