Let G be a graph with degree sequence ( dv). If the maximum degree of any subgraph induced by a neighborhood of G is at most m, then the independence number of G is at least $\sum\limits_v {f_{m + 1} \left( {d_v } \ri...Let G be a graph with degree sequence ( dv). If the maximum degree of any subgraph induced by a neighborhood of G is at most m, then the independence number of G is at least $\sum\limits_v {f_{m + 1} \left( {d_v } \right)} $ , where fm+1( x) is a function greater than $\frac{{log\left( {x/\left( {m + 1} \right)} \right) - 1}}{x}for x > 0$ for x> 0. For a weighted graph G = ( V, E, w), we prove that its weighted independence number (the maximum sum of the weights of an independent set in G) is at least $\sum\limits_v {\frac{{w_v }}{{1 + d_v }}} $ where wv is the weight of v.展开更多
In[1],P.Paulraja posed the following problem:Let G be a 2-connected graph suchthat δ(G)≥3,where δ(G)denotes the minimum degree of G.If each edge of G lies on either a cycle oflength 3 or a cycle of length 4,is it t...In[1],P.Paulraja posed the following problem:Let G be a 2-connected graph suchthat δ(G)≥3,where δ(G)denotes the minimum degree of G.If each edge of G lies on either a cycle oflength 3 or a cycle of length 4,is it true that G has a spanning Eulerian subgraph?A related case inwhich δ(G)≥4 is settled affairmatively in this paper.展开更多
基金Li is supported in part by the National Natural Science Foundation of China (Grant No. 19871023) Science Foundation of the Education Ministry of China "333" Foundation and NSF of Jiangsu Province. Zang is supported in part by an RGC earmarked researc
文摘Let G be a graph with degree sequence ( dv). If the maximum degree of any subgraph induced by a neighborhood of G is at most m, then the independence number of G is at least $\sum\limits_v {f_{m + 1} \left( {d_v } \right)} $ , where fm+1( x) is a function greater than $\frac{{log\left( {x/\left( {m + 1} \right)} \right) - 1}}{x}for x > 0$ for x> 0. For a weighted graph G = ( V, E, w), we prove that its weighted independence number (the maximum sum of the weights of an independent set in G) is at least $\sum\limits_v {\frac{{w_v }}{{1 + d_v }}} $ where wv is the weight of v.
基金The present work is supported by the National Natural Science Foundation of China
文摘In[1],P.Paulraja posed the following problem:Let G be a 2-connected graph suchthat δ(G)≥3,where δ(G)denotes the minimum degree of G.If each edge of G lies on either a cycle oflength 3 or a cycle of length 4,is it true that G has a spanning Eulerian subgraph?A related case inwhich δ(G)≥4 is settled affairmatively in this paper.
