奇偶符号Harary图的rna数

奇偶符号图的概念最初是由Acharya和Kureethara提出的,随后有Zaslavsky等人相继研究。设(G,σ)是n个顶点的符号图,如果能够对(G,σ)中的个顶点等价转换得到(G,+),则称(G,σ)是一个奇偶符号图,并称σ是G的一个奇偶符号。Σ-(G)定义为在图G的所有可能奇偶符号σ下,(G,σ)的负边数的集合。图G的rna数σ-(G)定义为:σ-(G)=minΣ-(G)。本文研究了Harary图Hk,n的rna数。我们计算出了σ-(H3,n),σ-(H4,n)和σ-(Hk,k+2)的精确值。对于Hk,n的其他情况,我们给出其rna数的一个上下界:。

有序流水作业时间表问题是NP-困难的

讨论两台机器上的有序流水作业时间表问题 ,证明两台机器上的有序流水作业时间表问题是NP -困难的 .