فهرست مطالب

Transactions on Combinatorics
Volume:10 Issue: 3, Sep 2021

  • تاریخ انتشار: 1400/04/16
  • تعداد عناوین: 5
|
  • Batmend Horoldagva, Tsend Ayush Selenge *, Lkhagva Buyantogtokh, Shiikhar Dorjsembe Pages 137-148

    The graph invariant $RM_2$‎, ‎known under the name reduced second Zagreb index‎, ‎is defined as $RM_2(G)=sum_{uvin E(G)}(d_G(u)-1)(d_G(v)-1)$‎, ‎where $d_G(v)$ is the degree of the vertex $v$ of the graph $G$‎. ‎In this paper‎, ‎we give a tight upper bound of $RM_2$ for the class of graphs of order $n$ and size $m$ with at least one dominating vertex‎. ‎Also‎, ‎we obtain sharp upper bounds on $RM_2$ for all graphs of order $n$ with $k$ dominating vertices and for all graphs of order $n$ with $k$ pendant vertices‎. ‎Finally‎, ‎we give a sharp upper bound on $RM_2$ for all $k$-apex trees of order $n$‎. ‎Moreover‎, ‎the corresponding extremal graphs are characterized‎.

    Keywords: ‎Reduced second Zagreb index‎, ‎pendant vertex‎, ‎dominating vertex‎, ‎$k$-apex tree
  • Neda Mohammadi, Mehdi Kadivar * Pages 149-163
    ‎The maximum clique problem (MCP) is to determine a complete subgraph of maximum cardinality in a graph‎. ‎MCP is a fundamental problem in combinatorial optimization and is noticeable for its wide range of applications‎. ‎In this paper‎, ‎we present two branch-and-bound exact algorithms for finding a maximum clique in an undirected graph‎. ‎Many efficient exact branch and bound maximum clique algorithms use approximate coloring to compute an upper bound on the clique number but‎, ‎as a new pruning strategy‎, ‎we show that local core number is more efficient‎. ‎Moreover‎, ‎instead of neighbors set of a vertex‎, ‎our search area is restricted to a subset of the set in each subproblem which speeds up clique finding process‎. ‎This subset is based on the core of the vertices of a given graph‎. ‎We improved the MCQ and MaxCliqueDyn algorithms with respect to the new pruning strategy and search area restriction‎. ‎Experimental results demonstrate that the improved algorithms outperform the previous well-known algorithms for many instances when applied to DIMACS benchmark and random graphs‎.
    Keywords: ‎Branch, bound‎, ‎Core number‎, ‎Maximum clique
  • Hatice Topcu * Pages 165-170
    $Kite_{n,p}$ denotes the kite graph that is obtained by appending complete graph with order $pgeq4$ to an endpoint of path graph with order $n-p$‎. ‎It is shown that $Kite_{n,p}$ is determined by its adjacency spectrum for all $p$ and $n$ [H‎. ‎Topcu and ‎S‎. ‎Sorgun‎, ‎The kite graph is determined by its adjacency spectrum‎, ‎Applied Math‎. ‎and Comp.‎, ‎330 (2018) 134--142]‎. ‎For $n-p=1$‎, ‎it is proven that $Kite_{n,p}$ is determined by its signless Laplacian spectrum when $ngeq4$‎, ‎$nneq5$ and is also determined by its distance spectrum when $ngeq4$ [K‎. ‎C‎. ‎Das and ‎M‎. ‎Liu‎, ‎Kite graphs are determined by their spectra‎, ‎Applied Math‎. ‎and Comp.‎, ‎297 (2017) 74--78]‎. ‎In this note‎, ‎we say that $Kite_{n,p}$ is determined by its Laplacian spectrum for $n-pleq2$‎.
    Keywords: ‎Laplacian matrix‎, ‎kite graph‎, ‎determined by spectrum
  • B. Basavanagoud *, Shruti Policepatil, Praveen Jakkannavar Pages 171-185
    A communication network can be considered to be highly vulnerable to disruption if the failure of few members (nodes or links) can result in no members being able to communicate with very many others‎. ‎These communication networks can be modeled through graphs‎. ‎There are several graph-theoretic parameters to describe the stability of graphs‎. ‎But‎, ‎these parameters are not sufficient to study stability of graphs‎. ‎This leads to the concept of integrity of a graph‎. ‎In this paper‎, ‎we obtain the integrity of some graph operations and some special graphs which can help us to reconstruct the given network in such a way that it is more stable than the earlier one‎.
    Keywords: Vulnerability‎, ‎connectivity‎, ‎integrity‎, ‎graph operations
  • Xiuwen Yang, Ligong Wang * Pages 187-200
    The concept of energy of a signed digraph is extended to iota energy of a signed digraph‎. ‎The energy of a signed digraph $S$ is defined by $E(S)=sum_{k=1}^n|{Re}(z_k)|$‎, ‎where ${Re}(z_k)$ is the real part of eigenvalue $z_k$ and $z_k$ is the eigenvalue of the adjacency matrix of $S$ with $n$ vertices‎, ‎$k=1, 2,ldots,n$‎. ‎Then the iota energy of $S$ is defined by $E(S)=sum_{k=1}^n|{Im}(z_k)|$‎, ‎where ${Im}(z_k)$ is the imaginary part of eigenvalue $z_k$‎. ‎In this paper‎, ‎we consider a special graph class for bicyclic signed digraphs $mathcal{S}_n$ with $n$ vertices which have two vertex-disjoint signed directed even cycles‎. ‎We give two iota energy orderings of bicyclic signed digraphs‎, ‎one is including two positive or two negative directed even cycles‎, ‎the other is including one positive and one negative directed even cycles‎.
    Keywords: ‎Orderings‎, ‎iota energy‎, ‎bicyclic signed digraphs