The minimax path location problem is to find a path P in a graph G such that the maximum distance d_(G)(v,P)from every vertex v∈V(G)to the path P is minimized.It is a well-known NP-hard problem in network optimizatio...The minimax path location problem is to find a path P in a graph G such that the maximum distance d_(G)(v,P)from every vertex v∈V(G)to the path P is minimized.It is a well-known NP-hard problem in network optimization.This paper studies the fixed-parameter solvability,that is,for a given graph G and an integer k,to decide whether there exists a path P in G such that max v∈V(G)d_(G)(v,P)≤k.If the answer is affirmative,then graph G is called k-path-eccentric.We show that this decision problem is NP-complete even for k=1.On the other hand,we characterize the family of 1-path-eccentric graphs,including the traceable,interval,split,permutation graphs and others.Furthermore,some polynomially solvable special graphs are discussed.展开更多
Motivated by Problem 164 proposed by Y. Berkovich and E. Zhmud＇ in their book ＂Characters of Finite Groups＂, we give a characterization of finite groups whose irreducible character codegrees are prime powers. This ...Motivated by Problem 164 proposed by Y. Berkovich and E. Zhmud＇ in their book ＂Characters of Finite Groups＂, we give a characterization of finite groups whose irreducible character codegrees are prime powers. This is based on a new kind of character graphs of finite groups associated with codegrees. Such graphs have close and obvious connections with character codegree graphs. For example, they have the same number of connected components. By analogy with the work of finite groups whose character graphs （associated with degrees） have no triangles, we conduct a result of classifying finite groups whose character graphs associated with codegrees have no triangles in the latter part of this paper.展开更多
In this paper, we construct a new class of finite groups whose common divisor graphs are complete graphs, while there is no prime dividing all the nontrivial degrees.
In this article, we prove that a finite solvable group with character degree graph containing at least four vertices has Fitting height at most 4 if each derived subgraph of four vertices has total degree not more tha...In this article, we prove that a finite solvable group with character degree graph containing at least four vertices has Fitting height at most 4 if each derived subgraph of four vertices has total degree not more than 8. We also prove that if the vertex set ρ（G） of the character degree graph △（G） of a solvable group G is a disjoint union ρ（G） =π1∪π2, where ｜πi｜≥2 and pi,qi∈πi for i = 1,2, and no vertex in πl is adjacent in △（G） to any vertex in π2 except for p1p2 and q1q2, then the Fitting height of G is at most 4.展开更多
文摘The minimax path location problem is to find a path P in a graph G such that the maximum distance d_(G)(v,P)from every vertex v∈V(G)to the path P is minimized.It is a well-known NP-hard problem in network optimization.This paper studies the fixed-parameter solvability,that is,for a given graph G and an integer k,to decide whether there exists a path P in G such that max v∈V(G)d_(G)(v,P)≤k.If the answer is affirmative,then graph G is called k-path-eccentric.We show that this decision problem is NP-complete even for k=1.On the other hand,we characterize the family of 1-path-eccentric graphs,including the traceable,interval,split,permutation graphs and others.Furthermore,some polynomially solvable special graphs are discussed.
文摘Motivated by Problem 164 proposed by Y. Berkovich and E. Zhmud＇ in their book ＂Characters of Finite Groups＂, we give a characterization of finite groups whose irreducible character codegrees are prime powers. This is based on a new kind of character graphs of finite groups associated with codegrees. Such graphs have close and obvious connections with character codegree graphs. For example, they have the same number of connected components. By analogy with the work of finite groups whose character graphs （associated with degrees） have no triangles, we conduct a result of classifying finite groups whose character graphs associated with codegrees have no triangles in the latter part of this paper.
基金Supported by Science Foundation of He’nan University of Technology(Grant Nos.2011BS043 and 2010BS048)Tianyuan Fund of Mathematics of China(Grant No.11226046)
文摘In this paper, we construct a new class of finite groups whose common divisor graphs are complete graphs, while there is no prime dividing all the nontrivial degrees.
文摘In this article, we prove that a finite solvable group with character degree graph containing at least four vertices has Fitting height at most 4 if each derived subgraph of four vertices has total degree not more than 8. We also prove that if the vertex set ρ（G） of the character degree graph △（G） of a solvable group G is a disjoint union ρ（G） =π1∪π2, where ｜πi｜≥2 and pi,qi∈πi for i = 1,2, and no vertex in πl is adjacent in △（G） to any vertex in π2 except for p1p2 and q1q2, then the Fitting height of G is at most 4.
