فهرست مطالب
Transactions on Combinatorics
Volume:5 Issue: 3, Sep 2016
- تاریخ انتشار: 1395/03/31
- تعداد عناوین: 5
-
-
Pages 1-9A 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
-
Pages 11-21Let 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
-
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
-
Pages 38-38Let 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
-
Pages 39-50The 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)