فهرست مطالب

Transactions on Combinatorics - Volume:8 Issue:2, 2019
  • Volume:8 Issue:2, 2019
  • تاریخ انتشار: 1398/03/11
  • تعداد عناوین: 4
|
  • Hilal A. Ganie * Pages 1-12
    ‎‎For a simple connected graph $G$ with $n$ vertices and $m$ edges‎, ‎let $overrightarrow{G}$ be a digraph obtained by giving an arbitrary direction to the edges of $G$‎. ‎In this paper‎, ‎we consider the skew Laplacian/skew adjacency matrix of the digraph $overrightarrow{G}$‎. ‎We obtain upper bounds for the skew Laplacian/skew adjacency spectral radius‎, ‎in terms of various parameters (like oriented degree‎, ‎average oriented degree) associated with the structure of the digraph $overrightarrow{G}$‎. ‎We also obtain upper and lower bounds for the skew Laplacian/skew adjacency spectral radius‎, ‎in terms of skew Laplacian/skew adjacency rank of the digraph $overrightarrow{G}$‎.
    Keywords: ‎Digraph‎, ‎skew Laplacian matrix‎, ‎skew Laplacian spectrum‎, ‎skew Laplacian spectral radius
  • Igor Milovanovic, M. Matejic, P. Milosevic, Emina Milovanovic, Akbar Ali * Pages 13-19
    ‎‎‎For a simple connected graph $G$ of order $n$ and size $m$‎, ‎the Laplacian energy of $G$ is defined as‎ ‎$LE(G)=sum_{i=1}^n|mu_i-frac{2m}{n}|$ where $mu_1‎, ‎mu_2,ldots‎,‎‎mu_{n-1}‎, ‎mu_{n}$‎ ‎are the Laplacian eigenvalues of $G$ satisfying $mu_1ge mu_2gecdots ge mu_{n-1}>‎ ‎mu_{n}=0$‎. ‎In this note‎, ‎some new lower bounds on the graph invariant $LE(G)$ are derived‎. ‎The obtained results are compared with some already known lower bounds of $LE(G)$‎.
    Keywords: ‎Laplacian eigenvalue‎, ‎Laplacian energy (of a‎ ‎graph)‎, ‎first Zagreb index
  • Mohammad Hamidi, Arsham Borumand Saeid * Pages 21-43
    This paper defines the concept of partitioned hypergraphs‎, ‎and enumerates the number of these hypergraphs and discrete complete hypergraphs‎. ‎A positive equivalence relation is defined on hypergraphs‎, ‎this relation establishes a connection between hypergraphs and graphs‎. ‎Moreover‎, ‎we define the concept of (extended) derivable graph‎. ‎Then a connection between hypergraphs and (extended) derivable graphs was investigated‎. ‎Via the positive equivalence relation on hypergraphs‎, ‎we show that some special trees are derivable graph and complete graphs are self derivable graphs‎.
    Keywords: (Hyper)graph, derivable graphs, positive equivalence relation
  • Ramin Javadi *, Farideh Khoeini Pages 45-51
    Given a graph $ G $, a graph $ F $ is said to be Ramsey for $ G $ if in every edge coloring of $F$ with two colors, there exists a monochromatic copy of $G$. The minimum number of edges of a graph $ F $ which is Ramsey for $ G $ is called the size-Ramsey number of $G$ and is denoted by $hat{r}(G)$. In 1983, Beck gave a linear upper bound (in terms of $n$) for $hat{r}(P_{n})$, where $ P_n $ is a path on $ n $ vertices, giving a positive answer to a question of ErdH{o}s. After that, different approaches were attempted by several authors to reduce the upper bound for $hat{r}(P_n)$ for sufficiently large $n$ and most of these approaches are based on the classic models of random graphs. Also, Haxell and Kohayakama in 1994 proved that the size Ramsey number of the cycle $ C_n $ is linear in terms $ n $, however the Szemeredi's regularity lemma is used in their proof and so no specific constant coefficient is provided. Here, we provide a method to obtain an upper bound for the size Ramsey number of a graph using good expander graphs such as Ramanujan graphs. In particular, we give an alternative proof for the linearity of the size Ramsey number of paths and cycles. Our method has two privileges in compare to the previous ones. Firstly, it proves the upper bound for every positive integer $n$ in comparison to the random graph methods which needs $ n $ to be sufficiently large. Also, due to the recent explicit constructions for bipartite Ramanujan graphs by Marcus, Spielman and Srivastava, we can constructively find the graphs with small sizes which are Ramsey for a given graph. We also obtain some results about the bipartite Ramsey numbers.
    Keywords: size Ramsey number, bipartite Ramsey number, bipartite Ramanujan graph