فهرست مطالب

Transactions on Combinatorics - Volume:8 Issue:4, 2019
  • Volume:8 Issue:4, 2019
  • تاریخ انتشار: 1398/09/10
  • تعداد عناوین: 5
|
  • Farzaneh Ramezani * Pages 1-9
    A signed graph $(G,sigma)$ is a graph‎ ‎together with an assignment of signs ${+,-}$ to its edges where‎ ‎$sigma$ is the subset of its negative edges‎. ‎There are a few variants of coloring and clique problems of‎ ‎signed graphs‎, ‎which have been studied‎. ‎An initial version known as vertex coloring of signed graphs is defined by Zaslavsky in $1982$‎. ‎Recently Naserasr et. al., in [R‎. ‎Naserasr‎, ‎E‎. ‎Rollova and E‎. ‎Sopena‎, ‎Homomorphisms of signed graphs‎, ‎J‎. ‎Graph Theory‎, 79‎‎ (2015) 178--212, have defined signed chromatic and signed clique numbers of signed graphs‎. ‎In this paper we consider the latter mentioned problems for signed interval graphs‎. ‎We prove that the coloring problem of signed‎ ‎interval graphs is NP-complete whereas their ordinary coloring‎ ‎problem (the coloring problem of interval graphs) is in P‎. ‎Moreover we prove that the signed clique problem of a‎ ‎signed interval graph can be solved in polynomial time‎. ‎We also consider the‎ ‎complexity of further related problems‎.
    Keywords: ‎Signed clique Problem‎, ‎Signed Interval Graphs‎, ‎Signed Coloring Problem
  • Zahra Kharaghani * Pages 11-21

    We consider some combinatorics of elliptic root systems of type $A_1$. In particular, with respect to a fixed reflectable base, we give a precise description of the positive roots in terms of a positivity theorem. Also the set of reduced words of the corresponding Weyl group is precisely described. These then lead to a new characterization of the core of the corresponding Lie algebra, namely we show that the core is generated by positive root spaces.

    Keywords: Elliptic root systems, Elliptic Lie algebras, Jordan algebras
  • Manjit Singh * Pages 23-33
    Let $mathcal{S}_q$ denote the group of all square elements in the multiplicative group $mathbb{F}_q^*$ of a finite field $mathbb{F}_q$ of odd characteristic containing $q$ elements‎. ‎Let $mathcal{O}_q$ be the set of all odd order elements of $mathbb{F}_q^*$‎. ‎Then $mathcal{O}_q$ turns up as a subgroup of $mathcal{S}_q$‎. ‎In this paper‎, ‎we show that $mathcal{O}_q=langle4rangle$ if $q=2t+1$ and‎, ‎$mathcal{O}_q=langle trangle $ if $q=4t+1$‎, ‎where $q$ and $t$ are odd primes‎. ‎Further‎, ‎we determine the coefficients of irreducible factors of $x^{2^nt}-1$ using generators of these special subgroups of $mathbb{F}_q^*$
    Keywords: ‎Polynomials over finite fields‎, ‎Cyclotomic polynomials‎, ‎Special groups
  • Mahdieh Azari * Pages 35-48
    ‎‎The generalized Zagreb index is an extension of both ordinary and‎ ‎variable Zagreb indices‎. ‎In this paper‎, ‎we present exact formulae‎ ‎for the values of the generalized Zagreb index for product graphs‎. ‎Results are applied to some graphs of general and chemical‎ ‎interest such as nanotubes and nanotori‎.
    Keywords: Vertex degree, graph operation, nanotube, nanotorus
  • Weige Xi, Ligong Wang * Pages 49-60

    Let G=(V(G),E(G)) be a digraph without loops and‎ ‎multiarcs‎, ‎where V(G)={v1,v2, …,vn} and E(G) are the‎ ‎vertex set and the arc set of G‎, ‎respectively‎. ‎Let d+i be the‎ ‎outdegree of the vertex vi‎. ‎Let A(G) be the adjacency matrix of‎ ‎G and D(G)=diag(d+1,d+2,…,d+n) be the‎ ‎diagonal matrix with outdegrees of the vertices of G‎. ‎Then we call‎ ‎Q(G)=D(G)+A(G) the signless Laplacian matrix of G‎. ‎The spectral‎ ‎radius of Q(G) is called the signless Laplacian spectral radius of‎ ‎G‎, ‎denoted by q(G)‎. ‎In this paper‎, ‎some upper bounds for q(G)‎ ‎are obtained‎. ‎Furthermore‎, ‎some upper bounds on‎ ‎q(G) involving outdegrees and the average 2-outdegrees of the‎ ‎vertices of G are also derived‎.

    Keywords: digraph, Signless Laplacian spectral radius, Upper bounds