Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the pseudoachromatic index of the complete graph III
78
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Let $ Pi_q $ be the projective plane of order $ q $, let $psi(m):=psi(L(K_m))$ the pseudoachromatic number of the complete line graph of order $ m $, let $ ain { 3,4,dots,tfrac{q}{2}+1 } $ and $ m_a=(q+1)^2-a $. In this paper, we improve the upper bound of $ psi(m) $ given by Araujo-Pardo et al. [J Graph Theory 66 (2011), 89--97] and Jamison [Discrete Math. 74 (1989), 99--115] in the following values: if $ xgeq 2 $ is an integer and $min {4x^2-x,dots,4x^2+3x-3}$ then $psi(m) leq 2x(m-x-1)$. On the other hand, if $ q $ is even and there exists $ Pi_q $ we give a complete edge-colouring of $ K_{m_a} $ with $(m_a-a)q$ colours. Moreover, using this colouring we extend the previous results for $a={-1,0,1,2}$ given by Araujo-Pardo et al. in [J Graph Theory 66 (2011), 89--97] and [Bol. Soc. Mat. Mex. (2014) 20:17--28] proving that $psi(m_a)=(m_a-a)q$ for $ ain {3,4,dots,leftlceil frac{1+sqrt{4q+9}}{2}rightrceil -1 } $.
rate research
Read More
The quadrilateral graph Q(G) is obtained from G by replacing each edge in G with two parallel paths of length 1 and 3, whereas the pentagonal graph W(G) is obtained from G by replacing each edge in G with two parallel paths of length 1 and 4. In this paper, closed-form formulas of resistance distance and Kirchhoff index for quadrilateral graph and pentagonal graph are obtained whenever G is an arbitrary graph.
A mixed graph $widetilde{G}$ is obtained by orienting some edges of $G$, where $G$ is the underlying graph of $widetilde{G}$. The positive inertia index, denoted by $p^{+}(G)$, and the negative inertia index, denoted by $n^{-}(G)$, of a mixed graph $widetilde{G}$ are the integers specifying the numbers of positive and negative eigenvalues of the Hermitian adjacent matrix of $widetilde{G}$, respectively. In this paper, we study the positive and negative inertia index of the mixed unicyclic graph. Moreover, we give the upper and lower bounds of the positive and negative inertia index of the mixed graph, and characterize the mixed graphs which attain the upper and lower bounds respectively.
The $g$-girth-thickness $theta(g,G)$ of a graph $G$ is the minimum number of planar subgraphs of girth at least $g$ whose union is $G$. In this paper, we determine the $6$-girth-thickness $theta(6,K_n)$ of the complete graph $K_n$ in almost all cases. And also, we calculate by computer the missing value of $theta(4,K_n)$.
The Wiener index of a connected graph is the summation of all distances between unordered pairs of vertices of the graph. In this paper, we give an upper bound on the Wiener index of a $k$-connected graph $G$ of order $n$ for integers $n-1>k ge 1$: [W(G) le frac{1}{4} n lfloor frac{n+k-2}{k} rfloor (2n+k-2-klfloor frac{n+k-2}{k} rfloor).] Moreover, we show that this upper bound is sharp when $k ge 2$ is even, and can be obtained by the Wiener index of Harary graph $H_{k,n}$.
An adjacent vertex distinguishing coloring of a graph G is a proper edge coloring of G such that any pair of adjacent vertices are incident with distinct sets of colors. The minimum number of colors needed for an adjacent vertex distinguishing coloring of G is denoted by $chi_a(G)$. In this paper, we prove that $chi_a(G)$ <= 5($Delta+2$)/2 for any graph G having maximum degree $Delta$ and no isolated edges. This improves a result in [S. Akbari, H. Bidkhori, N. Nosrati, r-Strong edge colorings of graphs, Discrete Math. 306 (2006), 3005-3010], which states that $chi_a(G)$ <= 3$Delta$ for any graph G without isolated edges.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
