Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn almost self-centered graphs and almost peripheral graphs
139
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
An almost self-centered graph is a connected graph of order $n$ with exactly $n-2$ central vertices, and an almost peripheral graph is a connected graph of order $n$ with exactly $n-1$ peripheral vertices. We determine (1) the maximum girth of an almost self-centered graph of order $n;$ (2) the maximum independence number of an almost self-centered graph of order $n$ and radius $r;$ (3) the minimum order of a $k$-regular almost self-centered graph and (4) the maximum size of an almost peripheral graph of order $n;$ (5) which numbers are possible for the maximum degree of an almost peripheral graph of order $n;$ (6) the maximum number of vertices of maximum degree in an almost peripheral graph of order $n$ whose maximum degree is the second largest possible. Whenever the extremal graphs have a neat form, we also describe them.
rate research
Read More
Characterizing graphs by their spectra is an important topic in spectral graph theory, which has attracted a lot of attention of researchers in recent years. It is generally very hard and challenging to show a given graph to be determined by its spectrum. In Wang~[J. Combin. Theory, Ser. B, 122 (2017):438-451], the author gave a simple arithmetic condition for a family of graphs being determined by their generalized spectra. However, the method applies only to a family of the so called emph{controllable graphs}; it fails when the graphs are non-controllable. In this paper, we introduce a class of non-controllable graphs, called emph{almost controllable graphs}, and prove that, for any pair of almost controllable graphs $G$ and $H$ that are generalized cospectral, there exist exactly two rational orthogonal matrices $Q$ with constant row sums such that $Q^{rm T}A(G)Q=A(H)$, where $A(G)$ and $A(H)$ are the adjacency matrices of $G$ and $H$, respectively. The main ingredient of the proof is a use of the Binet-Cauchy formula. As an application, we obtain a simple criterion for an almost controllable graph $G$ to be determined by its generalized spectrum, which in some sense extends the corresponding result for controllable graphs.
By using the Szemeredi Regularity Lemma, Alon and Sudakov recently extended the classical Andrasfai-Erd~os-Sos theorem to cover general graphs. We prove, without using the Regularity Lemma, that the following stronger statement is true. Given any (r-1)-partite graph H whose smallest part has t vertices, and any fixed c>0, there exists a constant C such that whenever G is an n-vertex graph with minimum degree at least ((3r-4)/(3r-1)+c)n, either G contains H, or we can delete at most Cn^(2-1/t) edges from G to yield an r-partite graph.
A subgraph $H$ of an edge-coloured graph is called rainbow if all of the edges of $H$ have different colours. In 1989, Andersen conjectured that every proper edge-colouring of $K_{n}$ admits a rainbow path of length $n-2$. We show that almost all optimal edge-colourings of $K_{n}$ admit both (i) a rainbow Hamilton path and (ii) a rainbow cycle using all of the colours. This result demonstrates that Andersens Conjecture holds for almost all optimal edge-colourings of $K_{n}$ and answers a recent question of Ferber, Jain, and Sudakov. Our result also has applications to the existence of transversals in random symmetric Latin squares.
We study the algorithmic properties of the graph class Chordal-ke, that is, graphs that can be turned into a chordal graph by adding at most k edges or, equivalently, the class of graphs of fill-in at most k. We discover that a number of fundamental intractable optimization problems being parameterized by k admit subexponential algorithms on graphs from Chordal-ke. We identify a large class of optimization problems on Chordal-ke that admit algorithms with the typical running time 2^{O(sqrt{k}log k)}cdot n^{O(1)}. Examples of the problems from this class are finding an independent set of maximum weight, finding a feedback vertex set or an odd cycle transversal of minimum weight, or the problem of finding a maximum induced planar subgraph. On the other hand, we show that for some fundamental optimization problems, like finding an optimal graph coloring or finding a maximum clique, are FPT on Chordal-ke when parameterized by k but do not admit subexponential in k algorithms unless ETH fails. Besides subexponential time algorithms, the class of Chordal-ke graphs appears to be appealing from the perspective of kernelization (with parameter k). While it is possible to show that most of the weighted variants of optimization problems do not admit polynomial in k kernels on Chordal-ke graphs, this does not exclude the existence of Turing kernelization and kernelization for unweighted graphs. In particular, we construct a polynomial Turing kernel for Weighted Clique on Chordal-ke graphs. For (unweighted) Independent Set we design polynomial kernels on two interesting subclasses of Chordal-ke, namely, Interval-ke and Split-ke graphs.
A Cayley graph over a group G is said to be central if its connection set is a normal subset of G. It is proved that for any two central Cayley graphs over explicitly given almost simple groups of order n, the set of all isomorphisms from the first graph onto the second can be found in time poly(n).
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
