Packings of the complete directed graph with m-circuits

A packing of the complete directed symmetric graph DKv with m-circuits, denoted by(v,m)-DCP, is defined to he a family of are-disjoint m-circuits of DK, such that any one arc of DKv occurs in at most one m circuit. The packing number P(v,m) is the maximum number of m-circults in such a packing. The packing problem is to determine the value P(v,m) for everyinteger v ≥ m. In this paper, the problem is reduced to the case m 6 ≤v≤2m-[(4m-3的平方极) 1/2],for any fixed even integer m≥4,In particular,the values of P（v,m） are completely determined for m=12,14 and 16.     

A logician's view of graph polynomials

Graph polynomials are graph parameters invariant under graph isomorphisms which take values in a polynomial ring with a fixed finite number of indeterminates. We study graph polynomials from a model theoretic point of view. In this paper we distinguish between the graph theoretic (semantic) and the algebraic (syntactic) meaning of graph polynomials. Graph polynomials appear in the literature either as generating functions, as generalized chromatic polynomials, or as polynomials derived via determinants of adjacency or Laplacian matrices. We show that these forms are mutually incomparable, and propose a unified framework based on definability in Second Order Logic. We show that this comprises virtually all examples of graph polynomials with a fixed finite set of indeterminates. Finally we show that the location of zeros and stability of graph polynomials is not a semantic property. The paper emphasizes a model theoretic view. It gives a unified exposition of classical results in algebraic combinatorics together with new and some of our previously obtained results scattered in the graph theoretic literature.     

A bound on judicious bipartitions of directed graphs

Judicious partitioning problems on graphs ask for partitions that bound several quantities simultaneously,which have received much attention lately.Scott(2005)asked the following natural question:What is the maximum constant cdsuch that every directed graph D with m arcs and minimum outdegree d admits a bipartition V(D)=V_1∪V_2 satisfying min{e(V_1,V_2),e(V_2,V_1)}cdm?Here,for i=1,2,e(V_i,V_3-i)denotes the number of arcs in D from V_i to V_3-i.Lee et al.(2016)conjectured that every directed graph D with m arcs and minimum outdegree at least d 2 admits a bipartition V(D)=V_1∪V_2 such that min{e(V_1,V_2),e(V_2,V_1)}≥((d-1)/(2(2 d-1))+o(1))m.In this paper,we show that this conjecture holds under the additional natural condition that the minimum indegree is also at least d.     

Applying a combinatorial determinant to count weighted cycle systems in a directed graph

One method for counting weighted cycle systems in a graph entails taking the determinant of the identity matrix minus the adjacency matrix of the graph. The result of this operation is the sum over cycle systems of −1 to the power of the number of disjoint cycles times the weight of the cycle system. We use this fact to reprove that the determinant of a matrix of much smaller order can be computed to calculate the number of cycle systems in a hamburger graph.     

A multicast routing algorithm based on searching in directed graph

Aiming at constructing a delay and delay variation bounded Steiner tree in the real-time streaming media communication, in this paper, we discuss a multicast routing algorithm based on searching a directed graph (MRASDH). During the process of the construction of the multicast tree, some nodes and links in the network topology do not affect the outcome of the constructed tree. Therefore, based on the thought of shrinking the search space through deleting these non-relative nodes and edges to the utmost, the ant algorithm is utilized to generate a directed sub-graph of the network topology for each destination node, in which each node owns a bounded out-degree. And all these sub-graphs can be merged into a new directed graph that serves as the new search space. In the new space, the simulated annealing algorithm is applied to obtain a multicast tree that satisfies the condition for the optimization. The performance analysis and simulation results demonstrate that this algorithm can effectively construct a delay and delay variation bounded multicast tree. They also show that the algorithm have lower time complexity than the current ones, which means a much better result would be achieved when the system scale rises greatly.     

A sufficient condition for the existence of an anti-directed 2-factor in a directed graph

Let D be a directed graph with vertex set V, arc set A, and order n. The graph underlyingD is the graph obtained from D by replacing each arc (u,v)∈A by an undirected edge {u,v} and then replacing each double edge by a single edge. An anti-directed (hamiltonian) cycleH in D is a (hamiltonian) cycle in the graph underlying D such that no pair of consecutive arcs in H form a directed path in D. An anti-directed 2-factor in D is a vertex-disjoint collection of anti-directed cycles in D that span V. It was proved in Busch et al. (submitted for publication) [3] that if the indegree and the outdegree of each vertex of D is greater than then D contains an anti-directed Hamilton cycle. In this paper we prove that given a directed graph D, the problem of determining whether D has an anti-directed 2-factor is NP-complete, and we use a proof technique similar to the one used in Busch et al. (submitted for publication) [3] to prove that if the indegree and the outdegree of each vertex of D is greater than then D contains an anti-directed 2-factor.     

A fractal graph model of capillary type systems

Abstract

We consider blood flow in a vessel with an attached capillary system. The latter is modelled with the help of a corresponding fractal graph whose edges are supplied with ordinary differential equations obtained by the dimension-reduction procedure from a three-dimensional model of blood flow in thin vessels. The Kirchhoff transmission conditions must be satisfied at each interior vertex. The geometry and physical parameters of this system are described by a finite number of scaling factors which allow the system to have self-reproducing solutions. Namely, these solutions are determined by the factors’ values on a certain fragment of the fractal graph and are extended to its rest part by virtue of these scaling factors. The main result is the existence and uniqueness of self-reproducing solutions, whose dependence on the scaling factors of the fractal graph is also studied. As a corollary we obtain a relation between the pressure and flux at the junction, where the capillary system is attached to the blood vessel. This relation leads to the Robin boundary condition at the junction and this condition allows us to solve the problem for the flow in the blood vessel without solving it for the attached capillary system.     

A new model of conflict analysis - the three dimensional graph model

The purpose of this paper is to put forward a new model of conflict analysis - the 3-D graph model and its stability analysis, including the three most important factors of conflict analysis. The rules concerning the movement of multiple players are still considered based on practical restrictions. Therefore the 3-D graph model may be used to solve real problems effectivity.     

On quadrilaterals in layers of the cube and extremal problems for directed and oriented graphs

Erdős has conjectured that every subgraph of the n‐cube Q_n having more than (1/2 + o(1))e(Q_n) edges will contain a 4‐cycle. In this note we consider ‘layer’ graphs, namely, subgraphs of the cube spanned by the subsets of sizes k − 1, k and k + 1, where we are thinking of the vertices of Q_n as being the power set of {1,…, n}. Observe that every 4‐cycle in Q_n lies in some layer graph. We investigate the maximum density of 4‐cycle free subgraphs of layer graphs, principally the case k = 2. The questions that arise in this case are equivalent to natural questions in the extremal theory of directed and undirected graphs. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 66–82, 2000     

A simple proof for folds on both sides in complexes of graph homomorphisms

In this paper we study implications of folds in both parameters of Lovász' Hom complexes. There is an important connection between the topological properties of these complexes and lower bounds for chromatic numbers. We give a very short and conceptual proof of the fact that if is a fold of , then Hom collapses onto Hom, whereas Hom collapses onto Hom.

We also give an easy inductive proof of the only nonelementary fact which we use for our arguments: if is a closure operator on , then collapses onto .

     

Bounding the crossing number of a graph in terms of the crossing number of a minor with small maximum degree

We show that if G has a minor M with maximum degree at most 4, then the crossing number of G in a surface Σ is at least one fourth the crossing number of M in Σ. We use this result to show that every graph embedded on the torus with representativity r ≥ 6 has Klein bottle crossing number at least ⌊2r/3⌋²/64. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 168–173, 2001     

A circular embedding of a graph in Euclidean 3-space

A spatial embedding of a graph G is an embedding of G into the 3-dimensional Euclidean space . J.H. Conway and C.McA. Gordon proved that every spatial embedding of the complete graph on 7 vertices contains a nontrivial knot. A linear spatial embedding of a graph is an embedding which maps each edge to a single straight line segment. In this paper, we construct a linear spatial embedding of the complete graph on 2n−1 (or 2n) vertices which contains the torus knot T(2n−5,2) (n4). A circular spatial embedding of a graph is an embedding which maps each edge to a round arc. We define the circular number of a knot as the minimal number of round arcs in among such embeddings of the knot. We show that a knot has circular number 3 if and only if the knot is a trefoil knot, and the figure-eight knot has circular number 4.     

A new AATP model with considering supply chain lead-times and resources and scheduling of the orders in flowshop production systems: A graph-theoretic view

The present study attempts to synchronize the scheduling problem with determining the advanced available-to-promise (AATP) in a flowshop system to enhance supplier profitability and service level. In the proposed model the AATP, scheduling and graph theory concept have been combined to find the optimum resource allocation and enable accurate estimations of machines scheduling, production costs and delivery dates. To find the near optimum solutions for the large size problems a genetic algorithm is developed, first the orders are ranked based on their scores which are estimated then the optimum cost is calculated by balancing profitability and constraints such as the availability of the machines or the available material in each workstation. Some computer simulated experiments are provided to evaluate the performance of the proposed algorithm.     

Deza graphs: A generalization of strongly regular graph

We consider the following generalization of strongly regular graphs. A graph G is a Deza graph if it is regular and the number of common neighbors of two distinct vertices takes on one of two values (not necessarily depending on the adjacency of the two vertices). We introduce several ways to construct Deza graphs, and develop some basic theory. We also list all diameter two Deza graphs which are not strongly regular and have at most 13 vertices.     

A lower bound on independence in terms of degrees

We prove a new lower bound on the independence number of a simple connected graph in terms of its degrees.     

Computationally modeling organizational learning and adaptability as resource allocation: An artificial adaptive systems approach

A framework for and a computational model of organizational behavior based on an artificial adaptive system (AAS) is presented. An AAS, a modeling approach based on genetic algorithms, enables the modeling of organizational learning and adaptability. This learning can be represented as decisions to allocate resources to the higher performing organizational agents (i.e., individuals, groups, departments, or processes, depending on the level of analysis) critical to the organization's survival in different environments. Adaptability results from the learning function enabling the organizations to change as the environment changes. An AAS models organizational behavior from a micro-unit perspective, where organizational behavior is a function of the aggregate actions and interactions of each of the individual agents of which the organization is composed. An AAS enables organizational decision making in a dynamic environment to be modeled as a satisficing process and not as a maximization process. To demonstrate the feasibility and usefulness of such an approach, a financial trading adaptive system (FTAS) organization is computationally modeled based on the AAS framework. An FTAS is an example of how the learning mechanism in an AAS can be used to allocate resources to critical individuals, processes, functions, or departments within an organization.     

Dynamic systems view of learning a three‐tiered theory in physics: robust learning outcomes as attractors

The process of learning scientific knowledge from the dynamic systems viewpoint is studied in terms probabilistic learning model (PLM), where learning accrues from foraging in the epistemic landscape. The PLM leads to the formation of attractor‐type regions of preferred models in an epistemic landscape. The attractor‐type states correspond to robust learning outcomes which are more probable than others. These can be assigned either to the high confidence in model selection or to the dynamic evolution of a learner's proficiency, which depends on the learning history. The results suggest that robust learning states are essentially context dependent, and that learning is a continuous development between these context dependent states. © 2016 Wiley Periodicals, Inc. Complexity 21: 259–267, 2016     

Empirically-based hypothetical learning trajectories for fraction concepts: Products of the Learning Through Activity research program

The Measurement Approach to Rational Number (MARN) Project, a project of the ongoing Learning Through Activity (LTA) research program, produced eleven hypothetical learning trajectories (HLTs) for promoting fraction concepts. Four of these HLTs are the subject of research reports. In this article, we present the other seven HLTs We judged that the data and analyses of these seven would not separately make sufficient contributions to merit individual research reports. However, presenting these seven HLTs together was intended to meet the following goals:1. To give a broad set of examples of HLTs developed based on the LTA theoretical framework.2. To complete a set of HLTs that provide a comprehensive example of HLTs built on prior HLTs.3. To make available for future research and development the full set of HLTs generated by the MARN Project.LTA researchers have focused on how learners abstract a concept through their mathematical activity and how the abstractions can be promoted. The MARN Project continued this inquiry with rigorous single-subject teaching experiments.