Record Details

The cone of balanced subgraphs

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title The cone of balanced subgraphs
 
Creator BHATTACHARYA, A
PELED, UN
SRINIVASAN, MK
 
Subject graphs
colored graphs
alternating walks and trails
tutte set
cycle cone
 
Description In this paper we study a 2-color analog of the cycle cone of a graph. Suppose the edges of a graph are colored red and blue. A nonnegative real vector on the edges is said to be balanced if the red sum equals the blue sum at every vertex. A balanced subgraph is a subgraph whose characteristic vector is balanced (i.e., red degree equals blue degree at every vertex). By a sum (respectively, fractional sum) of cycles we mean a nonnegative integral (respectively, nonnegative rational) combination of characteristic vectors of cycles. Similarly, we define sum and fractional sum of balanced subgraphs. We show that a balanced sum of cycles is a fractional sum of balanced subgraphs. (C) 2009
 
Publisher ELSEVIER SCIENCE INC
 
Date 2011-07-27T13:14:08Z
2011-12-26T12:57:11Z
2011-12-27T05:47:07Z
2011-07-27T13:14:08Z
2011-12-26T12:57:11Z
2011-12-27T05:47:07Z
2009
 
Type Article
 
Identifier LINEAR ALGEBRA AND ITS APPLICATIONS, 431(1-2), 266-273
0024-3795
http://dx.doi.org/10.1016/j.laa.2009.02.029
http://dspace.library.iitb.ac.in/xmlui/handle/10054/7231
http://hdl.handle.net/10054/7231
 
Language en