•Explored outsourcing attributes and alternatives in reverse logistics.•Developed a sustainable balanced scorecard for the selection of attributes/sub-attributes.•Proposed a graph theoretic approach to select the best alternative.•A case of mobile manufacturing firm is discussed for the illustration of the approach. Reverse logistics has become an important issue for most of the organizations due to increased flow of product returns and growing concern for the environment, legislation, and corporate social responsibility. Reverse logistics activities include product collection, inspection and sorting, disposition (reuse, repair, remanufacture or recycle), and redistribution of products. One of the important decisions is whether such activities must be outsourced partly or all must be outsourced or nothing must be outsourced. The articles on the selection of third party reverse logistics service providers are abundant but the articles on outsourcing reverse logistics fully or partly are very limited. The proposed study develops a framework for outsourcing decisions in reverse logistics by using graph theoretic approach. The ability of graph theoretic approach to consider interdependencies and maintaining hierarchical relationship among attributes and sub-attributes makes it an attractive approach. The attributes and sub-attributes were selected by combining four traditional balanced scorecard perspectives i.e. stakeholder, internal business process, learning and growth, and finance with triple bottom line aspects of sustainability known as sustainable balanced scorecard. By considering sustainable balanced scorecard based attributes and sub-attributes, organizations can ensure their contribution toward sustainability even after outsourcing the reverse logistics activities. The proposed framework is illustrated by case example of a mobile manufacturing firm. Scenario based alternatives were developed and “outsourcing index” were calculated for all the alternatives by evaluating permanent function using graph theoretic approach. The best alternative was selected based on the “outsourcing index”. The proposed framework will help managers and practitioners in outsourcing reverse logistics decisions.