فهرست مطالب

Transactions on Combinatorics - Volume:7 Issue: 3, Sep 2018

Transactions on Combinatorics
Volume:7 Issue: 3, Sep 2018

  • تاریخ انتشار: 1397/05/10
  • تعداد عناوین: 5
|
  • Saeid Bagheri *, Mahtab Koohi Kerahroodi Pages 1-18
    ýýIn this articleý, ýfor a lattice Lý, ýwe define and investigateý ýthe annihilator graph ag(L) of L which contains the zero-divisor graph of L as a subgraphý. ýAlsoý, ýfor a 0-distributive lattice Lý, ýwe study some properties of this graph such as regularityý, ýconnectednessý, ýthe diameterý, ýthe girth and its domination numberý. ýMoreoverý, ýfor a distributive lattice L with Z(L)≠{0}ý, ýwe show that ag(L)=Γ(L) if and only if L has exactly two minimal prime idealsý. ýAmong other thingsý, ýwe consider the annihilator graph ag(L) of the lattice L=(D(n),|) containing all positive divisors of a non-prime natural number n and we compute some invariants such as the domination numberý, ýthe clique number and the chromatic number of this graphý. ýAlsoý, ýfor this lattice we investigate some special cases in which ag(D(n)) or Γ(D(n)) are planarý, ýEulerian or Hamiltonian.
    Keywords: ??Distributive lattice, Annihilator graph, Zero-divisor graph
  • Fateme Shafiei * Pages 19-28
    The spectral excess theoremý, ýdue to Fiol and Garriga in 1997ý, ýis an important resultý, ýbecause it gives a good characterizationý ýof distance-regularity in graphsý. ýUp to nowý, ýsome authors have given some variations of this theoremý. ýMotivated by thisý, ýwe give the corresponding result by using the Laplacian spectrum for digraphsý. ýWe also illustrate this Laplacian spectral excess theorem for digraphs with few Laplacian eigenvalues and we show that any strongly connected and regular digraph that has normal Laplacian matrix with three distinct eigenvaluesý, ýis distance-regularý. ýHence such a digraph is strongly regular with girth g=2 or g=3ý.
    Keywords: ?A Laplacian spectral excess theorem?, ?Distance-regular digraphs?, ?Strongly regular digraphs
  • Huiwen Cheng *, Yan-Jing Li Pages 29-36
    An edge-cut F of a connected graph G is called aý ýrestricted edge-cut if G−F contains no isolated verticesý. ýThe minimum cardinality of all restricted edge-cutsý ýis called the restricted edge-connectivity λ′(G) of Gý. ýA graph G is said to be λ′-optimal if λ′(G)=ξ(G)ý, ýwhereý ýξ(G) is the minimum edge-degree of Gý. ýA graph is said toý ýbe super-λ′ if every minimum restricted edge-cut isolatesý ýan edgeý.
    ýIn this paperý, ýfirstý, ýwe provide a short proof of a previous theorem aboutý ýthe sufficientý ýcondition for λ′-optimality in triangle-free graphsý, ýwhich was given iný ý[Jý. ýYuan ýandý ýAý. ýLiuý, ýSufficient conditions for λk-optimality in triangle-freeý ýgraphsý, ýDiscrete Mathý., ý310 (2010) 981--987]ý. ýSecondý, ýwe generalize a knowný ýresult about the sufficientý ýcondition for triangle-free graphs being super-λ′ which was given byý ýShang et alý. ýin [Lý. ýShang ýandý ýH. Pý. ýZhangý, ýSufficient conditions for graphs to be λ′-optimal and super-λ′ý, Network}, 309 (2009) 3336--3345]ý.
    Keywords: ?Triangle-free?, ?restricted edge-cut?, ?super-ld?
  • Ranveer Singh *, Ravindra B. Bapat Pages 37-54
    Let G be a graph (directed or undirected) having k number of blocks B1,B2,\hdots,Bk. A B-partition of G is a partition consists of k vertex-disjoint subgraph (B1^,B1^,\hdots,Bk^) such that B^i is an induced subgraph of Bi for i=1,2,\hdots,k. The terms ∏ki=1det(B^i), ∏ki=1per(B^i) represent the det-summands and the per-summands, respectively, corresponding to the B-partition (B1^,B1^,\hdots,Bk^). The determinant (permanent) of a graph having no loops on its cut-vertices is equal to the summation of the det-summands (per-summands), corresponding to all possible B-partitions. In this paper, we calculate the determinant and the permanent of classes of graphs such as block graph, block graph with negatives cliques, signed unicyclic graph, mixed complete graph, negative mixed complete graph, and star mixed block graphs.
    Keywords: mathcalB-partition, signed graph, mixed block graph
  • Sumaira Hafeez, Mehtab Khan* Pages 55-73
    The eigenvalues of a digraph are the eigenvalues of its adjacency matrix. The iota energy of a digraph is recently defined as the sum of absolute values of imaginary part of its eigenvalues. In this paper, we extend the concept of iota energy of digraphs to weighted digraphs. We compute the iota energy formulae for the positive and negative weight directed cycles. We also characterize the unicyclic weighted digraphs with cycle weight r∈[−1,1]∖{0} having minimum and maximum iota energy. We obtain well known McClelland upper bound for the iota energy of weighted digraphs. Finally, we find the class of noncospectral equienergetic weighted digraphs.
    Keywords: Weighted digraphs, Extremal energy, Equienergetic weighted digraphs