فهرست مطالب

Transactions on Combinatorics - Volume:5 Issue: 3, Sep 2016

Transactions on Combinatorics
Volume:5 Issue: 3, Sep 2016

  • تاریخ انتشار: 1395/03/31
  • تعداد عناوین: 5
|
  • Doost Ali Mojdeh, A. Sayed, Khalkhali, Hossein Abdollahzadeh Ahangar*, Yancai Zhao Pages 1-9
    A set S of vertices in a graph G=(V,E) is called a totalý ýk -distance dominating set if every vertex in V is withiný ýdistance k of a vertex in S ý. ýA graph G is total k -distanceý ýdomination-critical if γ k t (Gý−ýx)
    Keywords: ýDistance dominationý, ýtotalý ýk, distance dominating setý, ýtotal k, distanceý ýdomination, critical
  • Wai Chee Shiu* Pages 11-21
    Let G=(V,E) be a simple graphý. ýAn edge labeling f:E→{0,1} induces a vertex labeling f :V→Z 2 defined by f (v)≡∑ uv∈E f(uv)(mod2) for each v∈V ý, ýwhere Z 2 ={0,1} is the additive group of order 2ý. ýFor i∈{0,1} ý, ýletý ýe f (i)=|f −1 (i)| and v f (i)=|(f ) −1 (i)| ý. ýA labeling f is called edge-friendly ifý ý|e f (1)−e f (0)|≤1 ý. ýI f (G)=v f (1)−v f (0) is called the edge-friendly index of G under an edge-friendly labeling f ý. ýExtreme values of edge-friendly index of complete bipartite graphs will be determinedý.
    Keywords: ýEdge, friendly indexý, ýedge, friendly labelingý, ýcomplete bipartite graph
  • Mehdi Kadivar* Pages 23-31
    ýWe give an algorithmý, ýcalled T ∗ý, ýfor finding the k shortest simple paths connecting a certainý ýpair of nodesý, ýs and t ý, ýin a acyclic digraphý. ýFirst the nodes of the graph are labeled according to the topological orderingý. ýThen for node i an ordered list of simple s−i paths is createdý. ýThe length of the list is at most k and it is created by using tournament treesý. ýWe prove the correctness of T∗ and show that its worst-case complexity is O(m鉹梁) in which n is the number of nodes and m is the number of arcs and d ¯ is the mean degree of the graphý. ýThe algorithm has a space complexity of O(kn) which entails an important improvement in space complexityý. ýAn experimental evaluation of T ∗ is presented which confirms the advantage of our algorithm compared to theý ýmostefficient k shortest paths algorithms known so farý.
    Keywords: k shortest path problemý, ýcomplexity of algorithmsý, ýranking of paths
  • Nasser Hajisharifi*, Abolfazl Tehranian Pages 38-38
    Let G be a finite simple graph on the vertex set V(G) and let S⊆V(G) . Adding a whisker to G at x means adding a new vertex y and edge xy to G where x∈V(G) . The graph G∪W(S) is obtained from G by adding a whisker to every vertex of S . We prove that if G∖S is either a graph with no chordless cycle of length other than 3 or 5 , chordal graph or C 5 , then G∪W(S) is a vertex decomposable graph.
    Keywords: vertex decomposable, shellabel, Cohen, Macaulay
  • Yaoping Mao*, Zhao Wang, Ivan Gutman Pages 39-50
    The Wiener index W(G) of a connected graph G ý ýis defined as W(G)=∑ u,v∈V(G) d G (u,v) ý ýwhere d G (u,v) is the distance between the vertices u and v ofý ýG ý. ýFor S⊆V(G) ý, ýthe Steiner distance d(S) ofý ýthe vertices of S is the minimum size of a connected subgraph ofý ýG whose vertex set is S ý. ýThe k -th Steiner Wiener indexý ýSW k (G) of G is defined asý ýSW k (G)=∑ |S|=k S⊆V(G) d(S) SWk(G)=∑|S|=kS⊆V(G)d(S)ý. ýWe establishý ýexpressions for the k -th Steiner Wiener index on the joiný, ýcoronaý, ýclusterý, ýlexicographical productý, ýand Cartesian product of graphsý.
    Keywords: ýDistance (in graph)ý, ýSteiner distance (in graph)ý, ýSteiner Wiener indexý, ýproduct (of graphs)