A labeled graph is an ordered pair (G, L) consisting of a graph G and its labeling L: V(G) → {1, 2, ..., n}, where n=|V(G)|. An increasing nonconsecutive path in a labeled graph (G, L) is a path (u 1, u 2, ..., u k)...A labeled graph is an ordered pair (G, L) consisting of a graph G and its labeling L: V(G) → {1, 2, ..., n}, where n=|V(G)|. An increasing nonconsecutive path in a labeled graph (G, L) is a path (u 1, u 2, ..., u k), k≥1, in G such that L(u i)+1<L(u i+1) for all i=1, 2, ..., k?1. The total number of increasing nonconsecutive paths in (G, L) is denoted by d(G, L). The following open problem was proposed by Gargano, Lewinter and Malerba: obtaining a labeling L that produces the largest d(P n, L), where P n is a path of order n. Such a labeling is called optimal. The author have solved this problem. For each n ≥ 5 and for n=3, there are exactly four optimal labelings. Either of P 2, P 4 has exactly two optimal labelings. MR Subject Classification 05C38 Keywords labeled graph - increasing nonconsecutive paths展开更多
In this paper, we obtain the following result: Let k, n 1 and n 2 be three positive integers, and let G = (V 1,V 2;E) be a bipartite graph with |V1| = n 1 and |V 2| = n 2 such that n 1 ? 2k + 1, n 2 ? 2k + 1 and |n 1 ...In this paper, we obtain the following result: Let k, n 1 and n 2 be three positive integers, and let G = (V 1,V 2;E) be a bipartite graph with |V1| = n 1 and |V 2| = n 2 such that n 1 ? 2k + 1, n 2 ? 2k + 1 and |n 1 ? n 2| ? 1. If d(x) + d(y) ? 2k + 2 for every x ∈ V 1 and y ∈ V 2 with xy $ \notin $ E(G), then G contains k independent cycles. This result is a response to Enomoto’s problems on independent cycles in a bipartite graph.展开更多
文摘A labeled graph is an ordered pair (G, L) consisting of a graph G and its labeling L: V(G) → {1, 2, ..., n}, where n=|V(G)|. An increasing nonconsecutive path in a labeled graph (G, L) is a path (u 1, u 2, ..., u k), k≥1, in G such that L(u i)+1<L(u i+1) for all i=1, 2, ..., k?1. The total number of increasing nonconsecutive paths in (G, L) is denoted by d(G, L). The following open problem was proposed by Gargano, Lewinter and Malerba: obtaining a labeling L that produces the largest d(P n, L), where P n is a path of order n. Such a labeling is called optimal. The author have solved this problem. For each n ≥ 5 and for n=3, there are exactly four optimal labelings. Either of P 2, P 4 has exactly two optimal labelings. MR Subject Classification 05C38 Keywords labeled graph - increasing nonconsecutive paths
基金supported by the Foundation for the Distinguished Young Scholars of Shandong Province (Grant No.2007BS01021)the Taishan Scholar Fund from Shandong Province,SRF for ROCS,SEMNational Natural Science Foundation of China (Grant No.60673047)
文摘In this paper, we obtain the following result: Let k, n 1 and n 2 be three positive integers, and let G = (V 1,V 2;E) be a bipartite graph with |V1| = n 1 and |V 2| = n 2 such that n 1 ? 2k + 1, n 2 ? 2k + 1 and |n 1 ? n 2| ? 1. If d(x) + d(y) ? 2k + 2 for every x ∈ V 1 and y ∈ V 2 with xy $ \notin $ E(G), then G contains k independent cycles. This result is a response to Enomoto’s problems on independent cycles in a bipartite graph.
